TY - GEN
T1 - Permuted pattern matching on multi-track strings
AU - Katsura, Takashi
AU - Narisawa, Kazuyuki
AU - Shinohara, Ayumi
AU - Bannai, Hideo
AU - Inenaga, Shunsuke
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84872563834&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84872563834&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-35843-2_25
DO - 10.1007/978-3-642-35843-2_25
M3 - Conference contribution
AN - SCOPUS:84872563834
SN - 9783642358425
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 280
EP - 291
BT - SOFSEM 2013
T2 - 39th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2013
Y2 - 26 January 2013 through 31 January 2013
ER -