（字符串）最长公共字串（Longest-Common-SubString，LCS）

题目：

给定两个字符串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 ;
}