Longest Repeated Subsequence | This function mainly returns LCS ( str , str ) with a condition that same characters at same index are not considered . ; THIS PART OF CODE IS SAME AS BELOW POST . IT FILLS dp [ ] [ ] https : www . geeksforgeeks . org / longest - repeating - subsequence / OR the code mentioned above . ; THIS PART OF CODE FINDS THE RESULT STRING USING DP [ ] [ ] , Initialize result ; Traverse dp [ ] [ ] from bottom right ; If this cell is same as diagonally adjacent cell just above it , then same characters are present at str [ i - 1 ] and str [ j - 1 ] . Append any of them to result . ; Otherwise we move to the side that that gave us maximum result ; Since we traverse dp [ ] [ ] from bottom , we get result in reverse order . ; Driver Code
< ? php function longestRepeatedSubSeq ( $ str ) { $ n = strlen ( $ str ) ; $ dp = array ( array ( ) ) ; for ( $ i = 0 ; $ i <= $ n ; $ i ++ ) for ( $ j = 0 ; $ j <= $ n ; $ j ++ ) $ dp [ $ i ] [ $ j ] = 0 ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) for ( $ 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 ] ) ; $ res = " " ; $ i = $ n ; $ j = $ n ; while ( $ i > 0 && $ j > 0 ) { if ( $ dp [ $ i ] [ $ j ] == $ dp [ $ i - 1 ] [ $ j - 1 ] + 1 ) { $ res = $ res . $ str [ $ i - 1 ] ; $ i -- ; $ j -- ; } else if ( $ dp [ $ i ] [ $ j ] == $ dp [ $ i - 1 ] [ $ j ] ) $ i -- ; else $ j -- ; } return strrev ( $ res ) ; } $ str = " AABEBCDD " ; echo longestRepeatedSubSeq ( $ str ) ; ? >