Prefix table construction and conversion

Widmer Bland, Gregory Kucherov, W. F. Smyth

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Citations (Scopus)


The prefix table of a string x = x[1..n] is an array π = π[1..n] such that π[i] is the length of the longest substring beginning at i that equals a prefix of x. In this paper we describe and evaluate algorithms for prefix table construction, some previously proposed, others designed by us. We also describe and evaluate new linear-time algorithms for transformations between π and the border array.

Original languageEnglish
Title of host publicationCombinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers
Number of pages7
Publication statusPublished - 2013
Externally publishedYes
Event24th International Workshop on Combinatorial Algorithms, IWOCA 2013 - Rouen, France
Duration: 10 Jul 201312 Jul 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8288 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th International Workshop on Combinatorial Algorithms, IWOCA 2013


Dive into the research topics of 'Prefix table construction and conversion'. Together they form a unique fingerprint.

Cite this