最长公共子串
#include<iostream>
#include<string>
#include<vector>
using namespace std;
string LCS(string &str1, string &str2)
{
string result;
vector<int> num(str2.size(), 0);
int maxLength = 0, last = 0;
for(int i = 0; i < str1.size(); i++)
for(int j = 0; j < str2.size(); j++)
{
if(str2[j] == str1[i])
{
if(i == 0 || j == 0) num[j] = 1;
else num[j] = num[j-1] + 1;
if(num[j] > maxLength)
{
maxLength = num[j];
last = j;
}
}
}
cout << maxLength << endl << last;
for(int i = last+1-maxLength; i <= last; i++)
result += str2[i];
return result;
}
int main(int argc, const char * argv[]) {
// insert code here...
string str1,str2;
cin >> str1 >> str2;
if(str1.size() == 0 || str2.size() == 0) cout << "";
cout << LCS(str1, str2);
return 0;
}
