print the longest common subsequence code example
Example 1: longest common subsequence
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
"""
text1: horizontally
text2: vertically
"""
dp = [[0 for _ in range(len(text1)+1)] for _ in range(len(text2)+1)]
for row in range(1, len(text2)+1):
for col in range(1, len(text1)+1):
if text2[row-1]==text1[col-1]:
dp[row][col] = 1+ dp[row-1][col-1]
else:
dp[row][col] = max(dp[row-1][col], dp[row][col-1])
return dp[len(text2)][len(text1)]
Example 2: longest common subsequence codefroces
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1001;
int dp[MAX][MAX];
bool visited[MAX][MAX];
int x, y;
string s1, s2;
int lcs(int i, int j)
{
if(i == x || j == y)
return 0;
if(visited[i][j])
return dp[i][j];
visited[i][j] = true;
int ans = 0;
if(s1[i] == s2[j])
{
ans = max(ans, 1+lcs(i+1, j+1));
}
else
{
ans = max(ans, lcs(i+1, j));
ans = max(ans, lcs(i, j+1));
}
dp[i][j] = ans;
return ans;
}
int main()
{
cin >> x >> y;
cin >> s1 >> s2;
for(int i=0; i<=x; i++)
{
for(int j=0; j<=y; j++)
{
visited[i][j] = false;
}
}
cout << lcs(0, 0);
return 0;
}
Example 3: 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;
}