1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 using namespace std;
 5 
 6 int main(int argc, char** argv) {
 7     string t, a, b;
 8     cin >> t;
 9     // 输入字符串形为 "abcd;bcde", 以";"作为两个字符串的分隔, a,b两个字符串并不包含";"
10     int idx = t.find_first_of(';');
11     a = t.substr(0, idx);
12     b = t.substr(idx+1);
13     int sizeA = a.size(), sizeB = b.size();
14     vector<vector<int>> dp(sizeA + 1, vector<int>(sizeB + 1, 0));
15     // dp[i][j] 表示a字符串的前i个字符与b字符串的前j个字符的最长公共子串的长度
16     int maxLen = 0, startPos = 0;
17     // maxLen 记录两个字符串的最长公共子串的长度, startPos 记录最长公共子串在b字符串中的起始位置
18 
19     for(int i = 1; i <= sizeA; ++i) {
20         string temp;
21         for(int j = 1; j <= sizeB; ++j) {
22             if(a[i-1] == b[j-1]) {
23                 dp[i][j] = dp[i-1][j-1] + 1;
24                 if(dp[i][j] > maxLen) {
25                     maxLen = dp[i][j];
26                     startPos = j - maxLen;
27                 }
28             }
29         }
30     }
31     cout << maxLen << ' ' << b.substr(startPos, maxLen) << endl;
32     return 0;
33 }