题目：
给定两个字符串X，Y，求二者最长的公共子串，例如X=[aaaba]，Y=[abaa]。二者的最长公共子串为[aba]，长度为3。
子序列是不要求连续的，字串必须是连续的。
思路与代码：
1、简单思想：
- 遍历两个字符串X、Y，分别比较X的字串与Y的字串，求出最长的公共字串。
- 设X长度为m，Y长度为n，最长公共字串长度为len，则时间复杂度为O(m*n*len)，空间复杂度为O(1)
#include <iostream>
#include <vector> using namespace std; int getComLen(char *str1,char *str2){
int len=;
while(*str1 && *str2){
if(*(str1++)==*(str2++))
len++;
}
return len;
} int LCS1(char *str1,int len1,char *str2,int len2){
int maxlen=; // max length of LCS
int maxIndex=; // start position of LCS
int len;
for(int i=;i<len1;i++){
for(int j=;j<len2;j++){
len=getComLen(str1+i,str2+j);
if(len>maxlen){
maxlen=len;
maxIndex=i;
}
}
}
cout<<"Length of Longest Common Substring: "<<maxlen<<endl;
cout<<"LCS is: ";
for(int i=maxIndex;i<maxIndex+maxlen;i++)
cout<<str1[i];
cout<<endl;
return maxlen;
}
int main()
{
char str1[]="Chinese";
char str2[]="Chienglish";
int len1=sizeof(str1)/sizeof(str1[])-;
int len2=sizeof(str2)/sizeof(str2[])-;
cout << LCS1(str1,len1,str2,len2) << endl;
return ;
}
2、动态规划思想：
- 与最长字符子序列一样，最长字符字串一样可以通过动态规划来求解，不一样的是，字串是连续的。
- 假设dp[i][j]来表示以x[i]、y[j]结尾的公共子串长度(不是最长，最长的字串长度需要通过比较得到)，由于字串连续，x[i]和y[i]要么与前面的前面的公共字串构成新的字串，要么不能构成公共字串。
- 公共字串长度的状态转移方程如下：
初始状态：dp[i][j]=0 if i==0 || j==0
转移方程：dp[i][j] = dp[i-1][j-1]+1 if x[i-1]==y[j-1]
dp[i][j] = 0 if x[i-1]!=y[j-1]
- 最长公共字串长度以及最长公共字串，需要在求公共字串长度的过程中通过比较并记录下来，具体参考代码。
- 设X长度为m，Y长度为n，最长公共字串长度为len，则时间复杂度为O(m*n)，空间复杂度为O(m*n)
#include <iostream>
#include <vector> using namespace std; // dynamic programming
int LCS2(char *str1,int len1,char *str2,int len2){
vector<vector<int> > dp(len1+,vector<int>(len2+,));
int maxlen=; // max length of LCS
int maxIndex=; // start position of LCS
for(int i=;i<=len1;i++){
for(int j=;j<=len2;j++){
if(i== || j==)
dp[i][j]=;
else{
if(str1[i-]==str2[j-])
dp[i][j]=dp[i-][j-]+;
} if(dp[i][j]>maxlen){
maxlen=dp[i][j];
maxIndex=i-maxlen+;
}
}
}
cout<<"Length of Longest Common Substring: "<<maxlen<<endl;
cout<<"LCS is: ";
for(int i=maxIndex-;i<maxIndex-+maxlen;i++)
cout<<str1[i];
cout<<endl;
return maxlen;
} int main()
{
char str1[]="Chinese";
char str2[]="Chienglish";
int len1=sizeof(str1)/sizeof(str1[])-;
int len2=sizeof(str2)/sizeof(str2[])-;
cout << LCS2(str1,len1,str2,len2) << endl;
return ;
}