Bibliographic Details
| 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 |
