Longest Repeating Subsequence | C ++ program to find the longest repeating subsequence ; This function mainly returns LCS ( str , str ) with a condition that same characters at same index are not considered . ; Create and initialize DP table ; Fill dp table ( similar to LCS loops ) ; If characters match and indexes are not same ; If characters do not match ; Driver Program
#include <iostream> NEW_LINE #include <string> NEW_LINE using namespace std ; int findLongestRepeatingSubSeq ( string str ) { int n = str . length ( ) ; int dp [ n + 1 ] [ n + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) for ( int j = 0 ; j <= n ; j ++ ) dp [ i ] [ j ] = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= n ; j ++ ) { if ( str [ i - 1 ] == str [ j - 1 ] && i != j ) dp [ i ] [ j ] = 1 + dp [ i - 1 ] [ j - 1 ] ; else dp [ i ] [ j ] = max ( dp [ i ] [ j - 1 ] , dp [ i - 1 ] [ j ] ) ; } } return dp [ n ] [ n ] ; } int main ( ) { string str = " aabb " ; cout << " The ▁ length ▁ of ▁ the ▁ largest ▁ subsequence ▁ that " " ▁ repeats ▁ itself ▁ is ▁ : ▁ " << findLongestRepeatingSubSeq ( str ) ; return 0 ; }