A representation scheme and a searching algorithm for repetitions in a string
E.T. Lee, T.K. Ho · 2002
A representation scheme and a searching algorithm for all repetitions of the form xx in a finite string are presented. The algorithm is based on a careful arrangement of comparisons of adjacent substrings, with several important considerations to eliminate unnecessary steps. A divide-and-conquer strategy is used to reduce the problem size significantly. The run-time is O(n log n), and may be O(n) for some types of input. Possible further developments and applications are discussed.>