公共最长（连续）子串

公共最长（连续）子串

   思路很简单，动态规划就行了，设dp[i][j]为a串的0-i，b串的0-j的最长公共后缀长度。那么状态转移方程就是dp[i][j]=a[i]==b[i]?dp[i-1][j-1]:0

因为在i j为0时可能会出现dp[-1][-1]的情况，所以把dp数组后推一位，且dp数组会用到的最多就是dp[i-1][j-1],所以可以优化一下空间，把它变成一维数组从后往前dp，代码如下：

#include <bits/stdc++.h>
using namespace std;
char a[10000007],b[10000007];
int dp[10000007];
int main()
{
    while(1)
    {
        scanf("%s%s",a,b);
        int acd=strlen(a);//计算a和b字符串长度 
        int bcd=strlen(b);
        int maxn=0,jl;//maxn用来记录最长后缀，jl记录maxn出现时公共字符串位置。 
        memset(dp,0,(sizeof (int))*(bcd+1));//把dp置0，初始化。 
        for(int i=0;i<acd;i++)
        {
            for(int j=bcd-1;j>=0;j--)
            {
                dp[j+1]=a[i]==b[j]?dp[j]+1:0;//核心代码，状态转移。 
                if(maxn<dp[j+1])
                {
                    maxn=dp[j+1];//更新maxn与jl 
                    jl=i-maxn+1;
                }
            }
        }
        printf("%d\n",maxn);//输出 
        for(int i=jl;i<jl+maxn;i++)
        {
            printf("%c",a[i]);
        }
        printf("\n");
    }
}