Keywords (1)

Academic
Publications
Validating the Knuth-Morris-Pratt Failure Function, Fast and Online

Validating the Knuth-Morris-Pratt Failure Function, Fast and Online,10.1007/978-3-642-13182-0_13,Pawel Gawrychowski,Artur Jez,Lukasz Jez

Validating the Knuth-Morris-Pratt Failure Function, Fast and Online   (Citations: 2)
BibTex | RIS | RefWorks Download
Let 0 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 arrayA 0 (1::n), is there a wordw over arbitrary alphabet such that A 0 (i) = 0 w(i) for all i? Moreover, what is the minimum cardinality of required? We give an elementary and self-contained O(n logn) time algorithm for this problem, thus improving the previously known solution (6), which had no polynomial running time bound. Then, using both a deeper combinatorial insight into the structure of 0 and more advanced tools, we improve the running time to O(n).
Conference: Computer Science Symposium in Russia - CSR , pp. 132-143, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The reverse engineering problems, as well as the enumeration problems for other string data structures (suffix arrays, DAWG, etc.) have been extensively studied [12,13,14,15,16,17,18], whose solutions give us further insight concerning the data structures...

    I. Tomohiroet al. Verifying a Parameterized Border Array in O(n1.5) Time

    • ...Gawrychowski, Je˙ za nd Je˙ z [13] proposed a linear-time algorithm for checking whether a given array is the failure function of the Knuth-Morris-Pratt algorithm (see [16]) for some string...

    Jing Heet al. Reversing Longest Previous Factor Tables is Hard

Sort by: