Permuted Pattern Matching on Multi-track Strings
Permuted Pattern Matching on Multi-track Strings
复制标题
多轨字符串上的排列模式匹配
DOI：
10.1007/978-3-642-35843-2_25
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Takashi Katsura
中科院分区：
文献类型：
--
作者：
Yagi T;Ito D;Okada Y;Akamatsu W;Nihei Y;Yoshizaki T;Yamanaka S;Ok ano H;Suzuki N;Takashi Katsura
我们提出了一个新的变种的模式匹配的多组字符串，或多轨道，称为置换匹配，寻找一个多轨道模式的lengthmwithMtracks的出现，在一个多轨道文本的lengthnwithNtracks超过100。证明了该问题的求解时间为O（nNlog| Σ|）时间和O（mM+N）空间，当采用整数字母表时，时间和空间都是O（nN）。对于文本和模式中的字符串数目相等（全置换匹配）的情况，我们提出了一种称为多轨道后缀树的新索引结构，以及一个O（nNlog| Σ|）时间和O（nN）空间构造算法。利用这种结构，我们可以在O（mNlog）内解决全置换匹配问题|Σ| +occ）任何长度为m且出现了occ次的N个轨迹的多轨迹模式的时间。
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 lengthmwithMtracks, in a multi-track text of lengthnwithNtracks over Σ. We show that the problem can be solved inO(nNlog|Σ|) time andO(mM+N) space, and further inO(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 anO(nNlog|Σ|) time andO(nN) space construction algorithm. Using this structure, we can solve the full-permuted-matching problem inO(mNlog|Σ| +occ) time for any multi-track pattern of lengthmwithNtracks which occursocctimes.