Longest Common Extensions in Partial Words
| Autor: | Rachel Harred, Francine Blanchet-Sadri, Justin Lazarow |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783319295152 IWOCA |
| Popis: | The Longest Common Extension of a pair of positions (i, j) in a string, or word, is the longest substring starting at i and j. The LCE problem considers a word and a set of pairs of positions and computes for each pair in the set, the longest common extension starting at both positions in the pair. This problem finds applications in matching with don’t-care characters, approximate string searching, finding all exact or approximate tandem repeats, to name a few. From a practical point of view, Ilie et al. (Journal of Discrete Algorithms, 2010) looked for simple and efficient algorithms for the LCE problem. In this paper, we extend their analyses to partial words, strings with don’t-cares or holes. In this context, we compute the Longest Common Compatible Extension of each pair of positions (i, j) in a partial word, i.e., the longest substrings starting at i and j that are compatible. We show that our results match with those of total words (partial words without holes). We find that one of the simplest algorithms for implementing the LCE problem is optimal on average in this case. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|