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 log r）时间中索引二进制字符串的算法，其中n是长度，r是运行次数，Giaquinta和Grabowski（IPL，2013）给出了一个运行时间为O（n + r ^ 2）。在本文中，我们提出了一种新的非常简单的算法，该算法也可以在O（n + r ^ 2）的时间内运行，并且可以扩展，以使索引返回匹配的位置（如果有），或者该算法仅使用O（n）个空格位，而不使用O（n）个字。
展开▼
