3
$\begingroup$

I am wondering if a linear time algorithm exists to find the longest contiguous repeated substring in a given string? We could refer to this as the longest "contiguous-double", using the terminology of wye.bee from the link below:

Find all Contiguous-Doubles

Just to be clear, I am talking about a string $uu$ contained within a string $s$. There can be no overlap of $u$ with itself and no characters between the end of the first u and the start of the second.

A similar problem is the longest repeated substring problem, in the link below. This can be solved in linear time using suffix trees. These can be built and searched in linear time, see: Ukkonen's algorithm. However, for this problem the first string does not in general end immediately before the beginning of the second string.

Longest Repeated Substring

Another related problem is the longest palindromic substring. This can also be solved in linear time using Manacher's algorithm.

Longest Palindromic Substring

The ideas from Manacher's algorithm seem the most promising for application to finding the longest "contiguous-double". For example, let's say we're searching left to right. And say we've already found the double $ss$ in the text. Now, imagine we're looking for another double within the rightmost $s$. Then if in the leftmost $s$ we have already found a double of $n$ characters in length, we know that said double definitely exists in the rightmost $s$. So we only need to search $n+1$ and above. However, unlike in the case of Manacher's algorithm, this trick has its limitations. Particularly when we consider strings that exceed the bounds of $s$. It throws doubt on the existence of a linear-time algorithm.

I am surprised that I have not found any work on this problem in my research. It seems like an obvious extension to Manacher's algorithm. Has this problem been solved before?

$\endgroup$
1
$\begingroup$

What you are looking for is called a square factor of a string. Finding all square factors can be done in O(n lg n) [paper].

If the size of alphabet is bounded, then all square factors can be found in linear time [paper].

Although they didn't solve your problem exactly, you probably can find more relevant research from these two papers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.