Finding the longest repeating subsequence

Question

Given a string $s,ドル I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ such that $w=w' \cdot w' $. That is, $w$ is a string whose halves appear twice in a row. Note that $w$ is a subsequence of $s,ドル but not necessarily a substring.

Examples:

For 'ababccabdc' it will be 'abcabc', because 'abc'='abc' and 'abc' appears (at least) twice in 'ababccabdc'.

For 'addbacddabcd' one option is 'dddd' because 'dd' appears twice (I cannot use the same letter several times, but here i have 4 'd's so its ok), but its of lebngth 4. I can find a better one of length 8: 'abcdabcd', because 'abcd' is a substring of 'addbacddabcd' that appears twice.

I'm interested in finding the longest repeating subsequence. This is also called "finding the longest/largest square", but I've read many articles in which a square is defined for a substring and not for a subsequence.

I can easily use a brute force algorithm that will take $O(n^3)$ by iterating on all options for a breakpoint in the string, and then I will have two strings in which I'll be looking for largest/longest common subsequence, but each check will take $O(n^2)$ using a dynamic programming technique, so the entire time will be $O(n^3)$. I found a more efficient algorithm for longest common subsequence which takes $O(\frac{n^2}{\log n})$ , so the running time will be $O(\frac{n^3}{\log n})$.

I am looking for a more efficient algorithm for longest repeating subsequence problem. Perhaps my idea of iterating over all breakpoints wastes too much time, and can be reduced to less iterations. Or perhaps an algorithm with a different attitude can solve this problem.

I've searched in many journals and previous questions, and most of the results I found were about a substring and not about a subsequence.

I've also read that this can be done using suffix trees, but this too was relevant to substrings and I am not sure if such an idea can be extended for subsequence.

I'm looking for a solution that runs in time $O(n^2)$. If there exists one in time $O(n \cdot \log n)$ that will be even better (I am not sure if such exists).

• Pseudonym: Look up suffix trees or suffix arrays.
• j_random_hacker: It's very unlikely that an $o(n^2)$-time algorithm exists for this problem, since if it did, you could use it to beat the best known algorithm for finding the LCS of two length-$n$ strings $u$ and $v$ as follows: Form the string $xuxv,ドル where $x$ is $n+1$ copies of a character $ that does not appear in either $u$ or $v,ドル and then run your $o(n^2)$-time algorithm on it. Both "halves" of the longest repeating subsequence will necessarily begin with $x,ドル so one half comes from each of $u$ and $v,ドル solving the LCS problem.
• Evil: @j_random_hacker LCS could be solved in $\mathcal O(n+m)$ using Suffix Tree or in $\mathcal O(n\log n)$ using rolling hashes.
• j_random_hacker: @Evil: I don't yet see how, could you give a bit more detail? (Are you sure you're not thinking of Longest Common Substring, which can be solved in those time complexities?)
• Evil: @j_random_hacker I thought that you are comparing aimed $o(n^2)$ with LCS (consecutive), but here, as you mentioned, yes, I haven't even seen working solution in n^2 for Longest Common Subsequence (I have found one dynamic programming code, propagated over many pages, which is flawed, similar to downvoted answer). So simply I misunderstood your comment, sorry.

Answer 1

Here is a dynamic programming solution.

Suppose that the input string is $x_1\ldots x_n$. Create a table $T$ whose rows and columns are indexed by 0,ドル\ldots,n$ (where $n$ is the length of the string), populated by the rule $$ T[i,j] = \begin{cases} 0 & \text{if $i = 0$ or $j = 0$}, \\ T[i-1,j-1] + 1 & \text{if $x_i = x_j$ and $i \neq j$}, \\ \max(T[i-1,j],T[i,j-1]) & \text{otherwise}. \end{cases} $$ The answer is $T[n,n]$.

• j_random_hacker: Suppose we are at some $i, j$ with $i=j+1,ドル and the condition in your if statement is true. Then dp[i][j] = dp[i - 1][j - 1] + 1 implies that the character at position $i-1=j$ is part of both subsequences.
• Raphael: Welcome to Computer Science! Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions.
• Number945: @Raphael A recursive formula does not count as source code.
• Raphael: @BreakingBenjamin Depending on your language of choice, you can write down the given recurrence more or less literally. The point is that there is no explanation here.