Longest Common Subsequence
Find longest subsequence common to both strings.
Enter inputs and click Run
Status: Ready
Speed
Algorithm Logic
1function lcs(s1, s2):
2 m, n = len(s1), len(s2)
3 dp = table(m+1, n+1, 0)
4
5 for i from 1 to m:
6 for j from 1 to n:
7 if s1[i-1] == s2[j-1]:
8 dp[i][j] = 1 + dp[i-1][j-1]
9 else:
10 dp[i][j] = max(
11 dp[i-1][j],
12 dp[i][j-1]
13 )
14
15 return dp[m][n]