zbMATH — the first resource for mathematics

Detecting regularities on grammar-compressed strings. (English) Zbl 1312.68238
Summary: We address the problems of detecting and counting various forms of regularities in a string represented as a straight-line program (SLP) which is essentially a context free grammar in the Chomsky normal form. Given an SLP of size \(n\) that represents a string \(s\) of length \(N\), our algorithm computes all runs and squares in \(s\) in \(O(n^3 h)\) time and \(O(n^2)\) space, where \(h\) is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in \(O(n^3 h + g n h \log N)\) time and \(O(n^2)\) space, where \(g\) is the length of the gap. As one of the main components of the above solution, we propose a new technique called approximate doubling which seems to be a useful tool for a wide range of algorithms on SLPs. Indeed, we show that the technique can be used to compute the periods and covers of the string in \(O(n^2 h)\) time and \(O(n h(n + \log^2 N))\) time, respectively.

68W32 Algorithms on strings
68Q42 Grammars and rewriting systems
68R15 Combinatorics on words
Full Text: DOI
[1] Apostolico, A.; Breslauer, D., An optimal \(\mathcal{O}(\log \log N)\)-time parallel algorithm for detecting all squares in a string, SIAM J. Comput., 25, 6, 1318-1331, (1996) · Zbl 0864.68045
[2] Apostolico, A.; Breslauer, D.; Galil, Z., Parallel detection of all palindromes in a string, Theor. Comput. Sci., 141, 1&2, 163-173, (1995) · Zbl 0873.68039
[3] Bannai, H.; Gagie, T.; I, T.; Inenaga, S.; Landau, G. M.; Lewenstein, M., An efficient algorithm to test square-freeness of strings compressed by straight-line programs, Inf. Process. Lett., 112, 19, 711-714, (2012) · Zbl 1248.68575
[4] Bille, P.; Landau, G. M.; Raman, R.; Sadakane, K.; Satti, S. R.; Weimann, O., Random access to grammar-compressed strings, (Proc. SODA 2011, (2011)), 373-389 · Zbl 1375.68229
[5] Crochemore, M.; Ilie, L.; Rytter, W., Repetitions in strings: algorithms and combinatorics, Theor. Comput. Sci., 410, 50, 5227-5235, (2009) · Zbl 1180.68206
[6] Crochemore, M.; Rytter, W., Efficient parallel algorithms to test square-freeness and factorize strings, Inf. Process. Lett., 38, 2, 57-60, (1991) · Zbl 0736.68033
[7] Crochemore, M.; Rytter, W., Text algorithms, (1994), Oxford University Press · Zbl 0844.68101
[8] Jansson, J.; Peng, Z., Online and dynamic recognition of squarefree strings, Int. J. Found. Comput. Sci., 18, 2, 401-414, (2007) · Zbl 1119.68176
[9] Khvorost, L., Computing all squares in compressed texts, (Proceedings of the 2nd Russian Finnish Symposium on Discrete Mathematics, vol. 17, (2012)), 116-122
[10] Kolpakov, R.; Kucherov, G., Searching for gapped palindromes, Theor. Comput. Sci., 410, 51, 5365-5373, (2009) · Zbl 1187.68367
[11] Kolpakov, R. M.; Kucherov, G., Finding maximal repetitions in a word in linear time, (Proc. FOCS 1999, (1999)), 596-604
[12] Lifshits, Y., Processing compressed texts: A tractability border, (Proc. CPM, (2007)), 228-240 · Zbl 1138.68419
[13] Main, M. G., Detecting leftmost maximal periodicities, Discrete Appl. Math., 25, 1-2, 145-153, (1989) · Zbl 0683.68033
[14] Main, M. G.; Lorentz, R. J., An \(\mathcal{O}(n \log n)\) algorithm for finding all repetitions in a string, J. Algorithms, 5, 3, 422-432, (1984) · Zbl 0547.68083
[15] Manacher, G. K., A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string, J. Assoc. Comput. Mach., 22, 3, 346-351, (1975) · Zbl 0305.68027
[16] Matsubara, W.; Inenaga, S.; Ishino, A.; Shinohara, A.; Nakamura, T.; Hashimoto, K., Efficient algorithms to compute compressed longest common substrings and compressed palindromes, Theor. Comput. Sci., 410, 8-10, 900-913, (2009) · Zbl 1162.68038
[17] Miyazaki, M.; Shinohara, A.; Takeda, M., An improved pattern matching algorithm for strings in terms of straight-line programs, (Proc. CPM 1997, (1997)), 1-11
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.