最长公共子串

佚名 6年前 (2019-04-27) 随笔 1852人围观抢沙发百度已收录

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 using namespace std;
 5 int dp[100][100] = { 0 };
 6 int main(void)
 7 {
 8     string s1, s2;
 9     while (cin>>s1>>s2)
10     {
11         int biggest = 0;
12         int length1 = s1.length();
13         int length2 = s2.length();
14         int i, j;
15         for (j = 0; j <= length2; ++j)
16         {
17             dp[0][j] = 0;
18         }
19         for (i = 0; i <= length1; ++i)
20         {
21             dp[i][0] = 0;
22         }
23         for (i = 1; i <= length1; ++i)
24         {
25             for (j = 1; j <= length2; ++j)
26             {
27                 if (s1[i - 1] == s2[j - 1])
28                 {
29                     dp[i][j] = dp[i - 1][j - 1] + 1;
30                     if (dp[i][j] > biggest)
31                         biggest = dp[i][j];
32                 }
33                 else
34                     dp[i][j] = 0;
35             }
36         }
37         cout <<"最长公共子串长度为"<< biggest << endl;
38     }
39     return 0;
40 }