Validating the Knuth-Morris-Pratt Failure Function, Fast and Online View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Paweł Gawrychowski , Artur Jeż , Łukasz Jeż

ABSTRACT

Let π′w denote the failure function of the Knuth-Morris-Pratt algorithm for a word w. In this paper we study the following problem: given an integer array A′[1 .. n], is there a word w over an arbitrary alphabet Σ such that A′[i] = π′w[i] for all i? Moreover, what is the minimum cardinality of Σ required? We give an elementary and self-contained \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(n\log n)$\end{document} time algorithm for this problem, thus improving the previously known solution [8] with no polynomial time bound. Using both deeper combinatorial insight into the structure of π′ and more advanced tools, we further improve the running time to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(n)$\end{document}. More... »

PAGES

132-143

Book

TITLE

Computer Science – Theory and Applications

ISBN

978-3-642-13181-3
978-3-642-13182-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-13182-0_13

DOI

http://dx.doi.org/10.1007/978-3-642-13182-0_13

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1049455431


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Computer Science, University of Wroc\u0142aw", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Institute of Computer Science, University of Wroc\u0142aw"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gawrychowski", 
        "givenName": "Pawe\u0142", 
        "id": "sg:person.013657430751.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013657430751.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Computer Science, University of Wroc\u0142aw", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Institute of Computer Science, University of Wroc\u0142aw"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Je\u017c", 
        "givenName": "Artur", 
        "id": "sg:person.015252371751.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Computer Science, University of Wroc\u0142aw", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Institute of Computer Science, University of Wroc\u0142aw"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Je\u017c", 
        "givenName": "\u0141ukasz", 
        "id": "sg:person.011054455171.24", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011054455171.24"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "Let \u03c0\u2032w denote the failure function of the Knuth-Morris-Pratt algorithm for a word w. In this paper we study the following problem: given an integer array A\u2032[1 .. n], is there a word w over an arbitrary alphabet \u03a3 such that A\u2032[i]\u2009=\u2009\u03c0\u2032w[i] for all i? Moreover, what is the minimum cardinality of \u03a3 required? We give an elementary and self-contained \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{O}(n\\log n)$\\end{document} time algorithm for this problem, thus improving the previously known solution [8] with no polynomial time bound. Using both deeper combinatorial insight into the structure of \u03c0\u2032 and more advanced tools, we further improve the running time to \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{O}(n)$\\end{document}.", 
    "editor": [
      {
        "familyName": "Ablayev", 
        "givenName": "Farid", 
        "type": "Person"
      }, 
      {
        "familyName": "Mayr", 
        "givenName": "Ernst W.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-13182-0_13", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-13181-3", 
        "978-3-642-13182-0"
      ], 
      "name": "Computer Science \u2013 Theory and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "Knuth-Morris", 
      "Pratt algorithm", 
      "algorithm", 
      "integer arrays", 
      "time algorithm", 
      "polynomial time", 
      "combinatorial insights", 
      "advanced tools", 
      "alphabet \u03a3", 
      "minimum cardinality", 
      "cardinality", 
      "tool", 
      "failure function", 
      "function", 
      "word w", 
      "solution", 
      "time", 
      "fast", 
      "problem", 
      "array", 
      "insights", 
      "structure", 
      "word w.", 
      "paper"
    ], 
    "name": "Validating the Knuth-Morris-Pratt Failure Function, Fast and Online", 
    "pagination": "132-143", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1049455431"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-13182-0_13"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-13182-0_13", 
      "https://app.dimensions.ai/details/publication/pub.1049455431"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:50", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_379.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-13182-0_13"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-13182-0_13'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-13182-0_13'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-13182-0_13'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-13182-0_13'


 

This table displays all metadata directly associated to this object as RDF triples.

103 TRIPLES      23 PREDICATES      50 URIs      43 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-13182-0_13 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nfb656fa1b27c4f3fb2c71d8d89468f90
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description Let π′w denote the failure function of the Knuth-Morris-Pratt algorithm for a word w. In this paper we study the following problem: given an integer array A′[1 .. n], is there a word w over an arbitrary alphabet Σ such that A′[i] = π′w[i] for all i? Moreover, what is the minimum cardinality of Σ required? We give an elementary and self-contained \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(n\log n)$\end{document} time algorithm for this problem, thus improving the previously known solution [8] with no polynomial time bound. Using both deeper combinatorial insight into the structure of π′ and more advanced tools, we further improve the running time to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(n)$\end{document}.
7 schema:editor Nf4f3501ae6724fd1b373256d6732ec1f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N4456a96bb0c444fb924c63ab9df94ed9
12 schema:keywords Knuth-Morris
13 Pratt algorithm
14 advanced tools
15 algorithm
16 alphabet Σ
17 array
18 cardinality
19 combinatorial insights
20 failure function
21 fast
22 function
23 insights
24 integer arrays
25 minimum cardinality
26 paper
27 polynomial time
28 problem
29 solution
30 structure
31 time
32 time algorithm
33 tool
34 word w
35 word w.
36 schema:name Validating the Knuth-Morris-Pratt Failure Function, Fast and Online
37 schema:pagination 132-143
38 schema:productId N83bb7bb8333145ccbd0197de99bc4f33
39 N83ef914ff78d423cbc52d03866e672cf
40 schema:publisher N6bb805cff7884ef686b931f22fd7616f
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049455431
42 https://doi.org/10.1007/978-3-642-13182-0_13
43 schema:sdDatePublished 2022-05-10T10:50
44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
45 schema:sdPublisher N1e4db1967304449b9d46def369eaf017
46 schema:url https://doi.org/10.1007/978-3-642-13182-0_13
47 sgo:license sg:explorer/license/
48 sgo:sdDataset chapters
49 rdf:type schema:Chapter
50 N1421e5aa637745eaa44c56b32bef248c rdf:first sg:person.011054455171.24
51 rdf:rest rdf:nil
52 N1e4db1967304449b9d46def369eaf017 schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N3797cfee62fc475a907cda581f28c180 rdf:first Na8280555a3584a2c8ae5a2dba93dd4a4
55 rdf:rest rdf:nil
56 N4456a96bb0c444fb924c63ab9df94ed9 schema:isbn 978-3-642-13181-3
57 978-3-642-13182-0
58 schema:name Computer Science – Theory and Applications
59 rdf:type schema:Book
60 N6bb805cff7884ef686b931f22fd7616f schema:name Springer Nature
61 rdf:type schema:Organisation
62 N83bb7bb8333145ccbd0197de99bc4f33 schema:name dimensions_id
63 schema:value pub.1049455431
64 rdf:type schema:PropertyValue
65 N83ef914ff78d423cbc52d03866e672cf schema:name doi
66 schema:value 10.1007/978-3-642-13182-0_13
67 rdf:type schema:PropertyValue
68 Na3ab517bbdd342319f2a36f0fcbe10fb schema:familyName Ablayev
69 schema:givenName Farid
70 rdf:type schema:Person
71 Na8280555a3584a2c8ae5a2dba93dd4a4 schema:familyName Mayr
72 schema:givenName Ernst W.
73 rdf:type schema:Person
74 Ne1e90280b6854417b3cd166cdcab58c7 rdf:first sg:person.015252371751.76
75 rdf:rest N1421e5aa637745eaa44c56b32bef248c
76 Nf4f3501ae6724fd1b373256d6732ec1f rdf:first Na3ab517bbdd342319f2a36f0fcbe10fb
77 rdf:rest N3797cfee62fc475a907cda581f28c180
78 Nfb656fa1b27c4f3fb2c71d8d89468f90 rdf:first sg:person.013657430751.28
79 rdf:rest Ne1e90280b6854417b3cd166cdcab58c7
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
84 schema:name Artificial Intelligence and Image Processing
85 rdf:type schema:DefinedTerm
86 sg:person.011054455171.24 schema:affiliation grid-institutes:None
87 schema:familyName Jeż
88 schema:givenName Łukasz
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011054455171.24
90 rdf:type schema:Person
91 sg:person.013657430751.28 schema:affiliation grid-institutes:None
92 schema:familyName Gawrychowski
93 schema:givenName Paweł
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013657430751.28
95 rdf:type schema:Person
96 sg:person.015252371751.76 schema:affiliation grid-institutes:None
97 schema:familyName Jeż
98 schema:givenName Artur
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
100 rdf:type schema:Person
101 grid-institutes:None schema:alternateName Institute of Computer Science, University of Wrocław
102 schema:name Institute of Computer Science, University of Wrocław
103 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...