int lcs(string X, string Y, int m, int n) { if (m == 0 || n == 0) return 0; if (X[m - 1] == Y[n - 1]) return 1 + lcs(X, Y, m - 1, n - 1); else return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n)); } code example
Example: longest common subsequence
int maxSubsequenceSubstring(char x[], char y[],
int n, int m)
{
int dp[MAX][MAX];
// Initialize the dp[][] to 0.
for (int i = 0; i <= m; i++)
for (int j = 0; j <= n; j++)
dp[i][j] = 0;
// Calculating value for each element.
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// If alphabet of string X and Y are
// equal make dp[i][j] = 1 + dp[i-1][j-1]
if (x[j - 1] == y[i - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
// Else copy the previous value in the
// row i.e dp[i-1][j-1]
else
dp[i][j] = dp[i][j - 1];
}
}
// Finding the maximum length.
int ans = 0;
for (int i = 1; i <= m; i++)
ans = max(ans, dp[i][n]);
return ans;
}