Important papers have appeared recently on the problem of indexing binary strings for jumbled pattern matching, and further lowering the time bounds in terms of the input size would now be a breakthrough with broad implications. We can still make progress on the problem, however, by considering other natural parameters. Badkobeh et al. (IPL, 2013) and Amir et al. (TCS, 2016) gave algorithms that index a binary string in O(n + r^2 log r) time, where n is the length and r is the number of runs, and Giaquinta and Grabowski (IPL, 2013) gave one that runs in O(n + r^2) time. In this paper we propose a new and very simple algorithm that also runs in O(n + r^2) time and can be extended either so that the index returns the position of a match (if there is one), or so that the algorithm uses only O(n) bits of space instead of O(n) words.
展开▼
机译：最近出现了重要的论文对混乱模式匹配的索引二进制字符串的问题，并且进一步降低输入大小的时间界限现在是具有广泛含义的突破。然而，我们仍然可以通过考虑其他自然参数来取得进展。 Badkobeh等人。 （IPL，2013）和Amir等人。 （TCS，2016）给出了索引了O（n + r ^ 2 logr）时间的二进制字符串的算法，其中n是长度，r是运行的数量，而giaquinta和grabowski（ipl，2013）给出了一个在O（n + r ^ 2）时间内运行。在本文中，我们提出了一种新的和非常简单的算法，也可以在O（n + r ^ 2）时间内运行，并且可以扩展，以便索引返回匹配的位置（如果有一个），否则算法仅使用O（n）空间而不是O（n）字。
展开▼
