write a program to find the longest common subsequence of two string code example
Example 1: python lcs length
def lcs(X, Y):
n = len(Y)
m = len(X)
L = [[None]*(n + 1) for i in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0 :
L[i][j] = 0
elif 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])
return L[m][n]
Example 2: longest common subsequence
int maxSubsequenceSubstring(char x[], char y[],
int n, int m)
{
int dp[MAX][MAX];
for (int i = 0; i <= m; i++)
for (int j = 0; j <= n; j++)
dp[i][j] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (x[j - 1] == y[i - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = dp[i][j - 1];
}
}
int ans = 0;
for (int i = 1; i <= m; i++)
ans = max(ans, dp[i][n]);
return ans;
}