Md. Faizul Bari, Mohammad Sohel Rahman and Rifat Shahriyar
Finding all covers of an indeterminate string in O(n) time on average
Abstract: |
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(n^{2}) time and O(n) space complexity. |
Download article: | |||
PostScript | BibTeX reference |
Download presentation: |