求最长公共子序列长度 LCS

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 // 给定两个字符串s1和s2（长度均不超过1000），求出这两个字符串的最大公共子串的长度。
 7 //
 8 //【分析】情境类似求最长公共子序列长度问题，不过需要注意的是：所求子串中的字符需要在串s1和串s2中连续出现。
 9 //
10 // 例：s1=”abcad”
11 //
12 // s2=”abd”
13 //
14 // 它们的最长公共子序列长度为3（”abd”），而最大公共子串长度为2（”ab”）。
15 //
16 // 因此，定义dp[i][j]：串s1的前i个字符 和 串s2的前j个字符的最大公共子串长度，则s1…si+1和t1…tj+1对应的公共子串可能是：
17 //
18 // ①si+1=tj+1时：在s1…si 和 t1…tj的公共子串末尾追加si+1（即LCS长度+1）
19 //
20 // ②否则dp[i][j]=0。
21 //
22 // 分析可知状态转移方程：
23 //
24 // dp[i+1][j+1]=dp[i][j]+1, ①
25 //
26 //
27 
28 const int maxlen = 1010;
29 char s1[maxlen], s2[maxlen];
30 int dp[maxlen][maxlen]; // dp[i][j]为串s1的前i个字符和串s2的前j个字符的最大公共子串长度 0, ②
31 
32 int main()
33 {
34 int i, j;
35 int len1, len2, ret; // ret记录结果
36 cin >> s1 >> s2;
37 memset(dp, 0 , sizeof(dp)); // 初始化，刚开始LCS长度均为0
38 len1 = strlen(s1) ;
39 len2 = strlen(s2);
40 ret = 0;
41 for (i = 0; i < len1; i++)
42 {
43 for (j = 0; j < len2; j++)
44 {
45 if (s1[i] == s2[j])
46 {
47 dp[i + 1][j +1] = dp[i][j] + 1;
48 }
49 else
50 {
51 dp[i + 1][j + 1] = 0;
52 }
53 ret = max(ret, dp[i + 1][j + 1]); // 随时更新最大值
54 }
55 }
56 cout << ret;
57 return 0;
58 }