The Prague Stringology Conference 2008
Pavlos Antoniou, Maxime Crochemore, Costas S. Iliopoulos, Inuka Jayasekera and Gad M. Landau
Conservative String Covering of Indeterminate Strings
| Abstract: |
| We study the problem of finding local and global covers as well as seeds in conservative indeterminate strings. 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. A conservative indeterminate string, is an indeterminate string where the number of indeterminate symbols in the positions of the string, i.e. the non-solid symbols, is bounded by a constant κ. We present an algorithm for finding a conservative indeterminate pattern p in an indeterminate string t. Furthermore, we present algorithms for computing conservative coversand seeds of the string t. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |