（字符串）最长公共字串（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 ;

}