暴力求解最长公共子串

 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 
 5 string longestStr(string str1, string str2) {
 6     int len1 = str1.size();
 7     int len2 = str2.size();
 8     int i, j;
 9     int max = 0, num = 0, start = 0;
10     for (i = 0; i < len1; ++i) {
11         for (j = 0; j < len2; ++j) {
12             int start1 = i;
13             int start2 = j;
14             while ((start1 < len1 - 1)&&(start2 <= len2 -  1) && (str1[start1++] == str2[start2++])) {
15                 num++;
16             }
17             if (num > max) {
18                 max = num;
19                 start = i;
20             }
21             num = 0;
22         }
23 
24     }
25     string str;
26     str = str1.substr(start, max);
27     return str;
28 }
29 
30 int main() {
31     string str1 = "abccade";
32     string str2 = "agbccaar";
33     string str = longestStr(str1, str2);
34     cout << str << endl;
35     return 0;
36 }