A fast algorithm for finding the positions of all squares in a run-length encoded string

作者：Liu J J; Huang G S; Wang Y L^*

来源：Theoretical Computer Science, 2009, 410(38-40): 3942-3948.

DOI：10.1016/j.tcs.2009.05.032

• Squares
• Divide-and-conquer
• Repetition
• Run-length encoding

Squares are strings of the form win where in is any nonempty string. Main and Lorentz proposed an O(n log n)-time algorithm for finding the positions of all squares ill a string of length n. Based on their result, we show how to find the positions of all squares in a run-length encoded string in time O(N logN) where N is the number of runs in this string, provided that we do not explicitly compute at all "trivial squares" occurring within runs. The algorithm is optimal and its time complexity is independent of the length of the original uncompressed string.

• 出版日期2009-9-6