Validating the Knuth-Morris-Pratt Failure Function, Fast and Online.
Saved in:
| Title: | Validating the Knuth-Morris-Pratt Failure Function, Fast and Online. |
|---|---|
| Authors: | Gawrychowski, Paweł gawry@cs.uni.wroc.pl, Jeż, Artur aje@cs.uni.wroc.pl, Jeż, Łukasz lje@cs.uni.wroc.pl |
| Source: | Theory of Computing Systems. Feb2014, Vol. 54 Issue 2, p337-372. 36p. |
| Subjects: | Failure Analysis System (Computer system), Mathematical functions, Algorithms, Integers, Cardinal numbers, Combinatorics |
| Abstract: | Let $\pi'_{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 \mathinner {\ldotp \ldotp }n]$, is there a word w over an arbitrary alphabet Σ such that $A'[i]=\pi'_{w}[i]$ for all i? Moreover, what is the minimum cardinality of Σ required? We give an elementary and self-contained $\mathcal{O}(n\log n)$ time algorithm for this problem, thus improving the previously known solution (Duval et al. in Conference in honor of Donald E. Knuth, ), which had no polynomial time bound. Using both deeper combinatorial insight into the structure of π′ and advanced algorithmic tools, we further improve the running time to $\mathcal{O}(n)$. [ABSTRACT FROM AUTHOR] |
| Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 94095249 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Validating the Knuth-Morris-Pratt Failure Function, Fast and Online. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Gawrychowski%2C+Paweł%22">Gawrychowski, Paweł</searchLink><i> gawry@cs.uni.wroc.pl</i><br /><searchLink fieldCode="AR" term="%22Jeż%2C+Artur%22">Jeż, Artur</searchLink><i> aje@cs.uni.wroc.pl</i><br /><searchLink fieldCode="AR" term="%22Jeż%2C+Łukasz%22">Jeż, Łukasz</searchLink><i> lje@cs.uni.wroc.pl</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Theory+of+Computing+Systems%22">Theory of Computing Systems</searchLink>. Feb2014, Vol. 54 Issue 2, p337-372. 36p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Failure+Analysis+System+%28Computer+system%29%22">Failure Analysis System (Computer system)</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+functions%22">Mathematical functions</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Integers%22">Integers</searchLink><br /><searchLink fieldCode="DE" term="%22Cardinal+numbers%22">Cardinal numbers</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorics%22">Combinatorics</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Let $\pi'_{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 \mathinner {\ldotp \ldotp }n]$, is there a word w over an arbitrary alphabet Σ such that $A'[i]=\pi'_{w}[i]$ for all i? Moreover, what is the minimum cardinality of Σ required? We give an elementary and self-contained $\mathcal{O}(n\log n)$ time algorithm for this problem, thus improving the previously known solution (Duval et al. in Conference in honor of Donald E. Knuth, ), which had no polynomial time bound. Using both deeper combinatorial insight into the structure of π′ and advanced algorithmic tools, we further improve the running time to $\mathcal{O}(n)$. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=94095249 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00224-013-9522-8 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 36 StartPage: 337 Subjects: – SubjectFull: Failure Analysis System (Computer system) Type: general – SubjectFull: Mathematical functions Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Integers Type: general – SubjectFull: Cardinal numbers Type: general – SubjectFull: Combinatorics Type: general Titles: – TitleFull: Validating the Knuth-Morris-Pratt Failure Function, Fast and Online. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Gawrychowski, Paweł – PersonEntity: Name: NameFull: Jeż, Artur – PersonEntity: Name: NameFull: Jeż, Łukasz IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 02 Text: Feb2014 Type: published Y: 2014 Identifiers: – Type: issn-print Value: 14324350 Numbering: – Type: volume Value: 54 – Type: issue Value: 2 Titles: – TitleFull: Theory of Computing Systems Type: main |
| ResultId | 1 |
