The Prague Stringology Conference 2009

Md. Faizul Bari, Mohammad Sohel Rahman and Rifat Shahriyar

Finding all covers of an indeterminate string in O(n) time on average

We study the problem of finding all the covers of an indeterminate string. An indeterminate string is a sequence T = T[1]T[2]...T[n], where T[i] ⊆ Σ for each i, and Σ is a given alphabet of fixed size. Here we describe an algorithm for finding all the covers of a string x. The algorithm is applicable for both regular and indeterminate strings. Our algorithm starts with the border array and uses pattern matching technique of the Aho-Corasick Automaton to compute all the covers of x from the border array. On average the algorithm requires O(n) time to find out all the covers, where n is the length of x. Finally, we extend our algorithm to compute the cover array of x in O(n2) time and O(n) space complexity.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation