Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Gawrychowski, Pawel
Jez, Artur
Jez, Lukasz

dblp
dblp
dblp

Not MPG Author(s):

Jez, Lukasz

BibTeX cite key*:

GawrychowskiJez2014

Title

Title*:

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

Journal

Journal Title*:

Theory of Computing Systems

Journal's URL:

http://www.springer.com/computer/theoretical+computer+science/journal/224

Download URL
for the article:

http://link.springer.com/content/pdf/10.1007%2Fs00224-013-9522-8.pdf

Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:

http://www.springer.com

Publisher's
Address:

Berlin

ISSN:

1432-4350

Vol, No, pp, Date

Volume*:

54

Number:

2

Publishing Date:

February 2014

Pages*:

337-372

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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 .. n]$, is there
a word $w$ over an arbitrary alphabet $\Sigma$ such that $A'[i]=\pi'_w[i]$ for all $i$?
Moreover, what is the minimum cardinality of $\Sigma$ required?
We give an elementary and self-contained $\mathcal{O}(n\log 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 $\pi'$ and advanced algorithmic
tools, we further improve the running time to $\mathcal{O}(n)$.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{GawrychowskiJez2014,
AUTHOR = {Gawrychowski, Pawel and Jez, Artur and Jez, Lukasz},
TITLE = {Validating the Knuth-Morris-Pratt Failure Function, Fast and Online},
JOURNAL = {Theory of Computing Systems},
PUBLISHER = {Springer},
YEAR = {2014},
NUMBER = {2},
VOLUME = {54},
PAGES = {337--372},
ADDRESS = {Berlin},
MONTH = {February},
ISBN = {1432-4350},
}


Entry last modified by Artur Jez, 12/15/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
11/24/2014 06:27:06 PM
Revision
0.



Editor
Artur Jez



Edit Date
11/24/2014 06:27:06 PM