Longest Repeating Subsequence - GeeksforGeeks

Related: LeetCode 1044 - Longest Duplicate Substring
Longest Repeating Subsequence - GeeksforGeeks
Given a string, find length of the longest repeating subseequence such that the two subsequence don't have same string character at same position, i.e., any i'th character in the two subsequences shouldn't have the same index in the original string.

This problem is just the modification of Longest Common Subsequence problem. The idea is to find the LCS(str, str) where str is the input string with the restriction that when both the characters are same, they shouldn’t be on the same index in the two strings.

int findLongestRepeatingSubSeq(string str)

{

    int n = str.length();

    // Create and initialize DP table

    int dp[n+1][n+1];

    for (int i=0; i<=n; i++)

        for (int j=0; j<=n; j++)

            dp[i][j] = 0;

    // Fill dp table (similar to LCS loops)

    for (int i=1; i<=n; i++)

    {

        for (int j=1; j<=n; j++)

        {

            // If characters match and indexes are not same

            if (str[i-1] == str[j-1] && i!=j)

                dp[i][j] =  1 + dp[i-1][j-1];                              

            // If characters do not match

            else

                dp[i][j] = max(dp[i][j-1], dp[i-1][j]);

        }

    }

    return dp[n][n];

}

http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */

int lcs( char *X, char *Y, int m, int n )

{

   int L[m+1][n+1];

   int i, j;

  

   /* Following steps build L[m+1][n+1] in bottom up fashion. Note

      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */

   for (i=0; i<=m; i++)

   {

     for (j=0; j<=n; j++)

     {

       if (i == 0 || j == 0)

         L[i][j] = 0;

  

       else if (X[i-1] == Y[j-1])

         L[i][j] = L[i-1][j-1] + 1;

  

       else

         L[i][j] = max(L[i-1][j], L[i][j-1]);

     }

   }

    

   /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */

   return L[m][n];

}

Read full article from Longest Repeating Subsequence - GeeksforGeeks