ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
复制标题
DOI：
10.1142/s0129054112400175
复制
发表时间：
2012-02-01
影响因子：
0.8
通讯作者：
Liptak, Zsuzsanna
中科院分区：
文献类型：
--
作者：
Burcsi, Peter;Cicalese, Ferdinando;Liptak, Zsuzsanna
在有限序字母表Sigma = {a（1），. . .，a（sigma）}被定义为字符的多重性的向量，p（s）=（p（1），. . .，p（sigma）），其中p（i）=垂直条{j垂直条s（j）= a（i）}垂直条。Parikh向量q出现在s中，如果s有一个子串t，其中p（t）= q。在长度为n的文本s中搜索查询q的问题可以简单地用滑动窗口方法在O（n）时间内最优地解决。本文针对文本固定且大量查询随着时间的推移而到达的情况提出了两种新的算法，第一种算法只判断给定的Parikh向量是否出现在二进制文本中。它使用线性大小的数据结构，并在O（1）时间内决定每个查询。第二种算法在任意字母表上找到给定Parikh向量在文本中的所有出现，并且具有次线性的预期时间复杂度。更准确地说，我们提出了算法的两个变体，都使用O（n）大小的数据结构，每个都可以在O（n）时间内构造。第一个解决方案非常简单，易于实现，并且导致预期查询时间为O（n（sigma/log sigma）（1/2）log m/root m），其中m = Sigma（i）q（i）是具有Parikh向量q的字符串的长度。第二种算法使用小波树，并将预期运行时间提高到O（n（sigma/log sigma）（1/2）1 root m），即，乘以log m的系数。
The Parikh vector p(s) of a string s over a finite ordered alphabet Sigma = {a(1), . . . , a(sigma)} is defined as the vector of multiplicities of the characters, p(s) = (p(1), . . . , p(sigma)), where p(i) = vertical bar{j vertical bar s(j) = a(i)}vertical bar. Parikh vector q occurs in s if s has a substring t with p(t) = q. The problem of searching for a query q in a text s of length n can be solved simply and worst-case optimally with a sliding window approach in O(n) time. We present two novel algorithms for the case where the text is fixed and many queries arrive over time.The first algorithm only decides whether a given Parikh vector appears in a binary text. It uses a linear size data structure and decides each query in O(1) time. The preprocessing can be done trivially in Theta(n(2)) time.The second algorithm finds all occurrences of a given Parikh vector in a text over an arbitrary alphabet of size sigma >= 2 and has sub-linear expected time complexity. More precisely, we present two variants of the algorithm, both using an O(n) size data structure, each of which can be constructed in O(n) time. The first solution is very simple and easy to implement and leads to an expected query time of O(n(sigma/log sigma)(1/2) log m/root m), where m = Sigma(i) q(i) is the length of a string with Parikh vector q. The second uses wavelet trees and improves the expected runtime to O(n(sigma/log sigma)(1/2) 1 root m), i.e., by a factor of log m.