最长公共子串问题

 1 // 最长公共子串问题
 2 // dp解决
 3 // 状态转移方程： dp = 0 当str1[i-1] != str2[j-1], dp = dp[i-1][j-1] 当str1[i-1] == str2[j-1]
 4 
 5 #include <bits/stdc++.h>
 6 using namespace std;
 7 
 8 int longest_sub_string(char str1[], int len_str1, char str2[], int len_Str2)
 9 {
10     int dp[len_str1 + 1][len_Str2 + 1];
11     int res = 0;
12     for (int i = 0; i <= len_str1; i++) // 初始化dp数组第一列
13         dp[i][0] = 0;
14     for (int i = 1; i <= len_Str2; i++) // 初始化dp数组第一行
15         dp[0][i] = 0;
16     for (int i = 1; i <= len_str1; i++)
17         for (int j = 1; j <= len_Str2; j++)
18             if (str1[i-1] == str2[j-1])
19             {
20                 dp[i][j] = dp[i - 1][j - 1] + 1;
21                 res = max(res, dp[i][j]); //每次更新记录最大值
22             }
23             else //不相等的情况
24                 dp[i][j] = 0;
25     return res;
26 }
27 
28 int main()
29 {
30     // 输入12345 67345，输出3（345相同）
31     char str1[100], str2[100];
32     scanf("%s%s", str1, str2);
33     int lon = longest_sub_string(str1, strlen(str1), str2, strlen(str2));
34     printf("%d", lon);
35     return 0;
36 }