Validating the Knuth-Morris-Pratt Failure Function, Fast and Online
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).