Name
Abstract | ||
|---|---|---|
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 Sigma. We show that the problem can be solved in O(nN log |Sigma|) 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 |Sigma|) time and O(nN) space construction algorithm. Using this structure, we can solve the full-permuted-matching problem in O(mN log |Sigma|+ occ) time for any multi-track pattern of length m with N tracks which occurs occ times. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-35843-2_25 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Integer,Discrete mathematics,Combinatorics,Computer science,Spacetime,Suffix tree,Pattern matching,Alphabet | Conference | 7741 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.48 |
References | Authors | |
15 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takashi Katsura | 1 | 54 | 5.91 |
| Kazuyuki Narisawa | 2 | 33 | 6.82 |
| Ayumi Shinohara | 3 | 936 | 88.28 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Shunsuke Inenaga | 5 | 595 | 79.02 |