## Friday, June 24, 2016

### Longest Repeating Subsequence - GeeksforGeeks

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];`
`}`