2018sjtu-最长公共子串

题意理解：找出两个字符串的公共子串，且公共子串不包含数字

思路：参考最长公共子序列LCS的解题思路，用二维dp数组来表示以str1[i],str2[j]为结尾的两个字符串的最长公共子串。

当str1[i]==str2[j]时，dp[i][j]由dp[i-1][j-1]转移而来 若不相等，则dp[i][j]=0

状态表示：

dp[i][j]表示以str1的第i个字母结尾，且以str2的第j个字母结尾的公共子串的集合；属性为公共子串的最大长度

状态转移：

若str1[i]==str2[j]，则dp[i][j]=dp[i-1][j-1]+1

若str1[i]!=str2[j]，则dp[i][j]=0

base case：

dp[0-i][0]和dp[0][0-j]均为0，表示其中有一个串为空

细节：

若str1[i]/str2[j]为数字，则dp值为0

用maxlen存储枚举过程中得到的最长公共子串的长度，s1存储最长公共子串在str1中的结束位置。

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
string str1,str2;
const int N=1100;
int dp[N][N];


int main()
{
    while(cin>>str1>>str2)
    {
        int len1=str1.size();
        int len2=str2.size();
        //dp[i][j]的含义：
        //第一个子串以第i个字符结尾，第二个子串以第j个字符结尾，所有str1(1~i)str2(1~j)的最长公共子串的长度

        //初始化：若str1/str2以第0个字符结尾，说明为空串，不可能存在公共子串
        for(int i=0;i<len1;i++)
            dp[i][0]=0;

        for(int j=0;j<len2;j++)
            dp[0][j]=0;


        int maxlen=0;//记录最长公共子串的长度
        int s1=0;//记录最长公共子串在str1中的结束位置

        for(int i=1;i<=len1;i++)
        {
            for(int j=1;j<=len2;j++)
            {
                if(str1[i-1]<='9'&&str1[i-1]>='0'||str2[j-1]<='9'&&str2[j-1]>='0')//排除数字的影响
                {
                    dp[i][j]=0;
                    continue;
                }

                if(str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1]+1;

                else dp[i][j]=0;


                if(dp[i][j]>maxlen)
                {
                    maxlen=dp[i][j];//记录最长长度
                    s1=i-1;//dp的位序比字符串多1
                }
            }
        }

        cout<<str1.substr(s1-maxlen+1,maxlen)<<endl;
    }
    return 0;
}