de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

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

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons118149

Gawrychowski,  Paweł
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons79297

Jeż,  Artur
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Gawrychowski, P., Jeż, A., & Jeż, Ł. (2013). Validating the Knuth-Morris-Pratt Failure Function, Fast and Online. Theory of Computing Systems, 54(2), 337-372. doi:10.1007/s00224-013-9522-8.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0024-558B-8
Zusammenfassung
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 \mathcalO}(nłog n) time algorithm for this problem, thus improving the previously known solution, 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).