Permuted Pattern Matching on Multi-track Strings
| Autor: | Ayumi Shinohara, Kazuyuki Narisawa, Takashi Katsura, Hideo Bannai, Shunsuke Inenaga |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783642358425 SOFSEM |
| DOI: | 10.1007/978-3-642-35843-2_25 |
| Popis: | We propose a new variant of pattern matching on a multi-set of strings, or multi-tracks, called permuted-matching, that looks for occurrences of a multi-track pattern of length m with M tracks, in a multi-track text of length n with N tracks over Σ. We show that the problem can be solved in O(nNlog|Σ|) time and O(mM + N) space, and further in O(nN) time and space when assuming an integer alphabet. For the case where the number of strings in the text and pattern are equal (full-permuted-matching), we propose a new index structure called the multi-track suffix tree, as well as an O(nN log|Σ|) time and O(nN) space construction algorithm. Using this structure, we can solve the full-permuted-matching problem in O(mN log|Σ| + occ) time for any multi-track pattern of length m with N tracks which occurs occ times. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|