计算a、b字符串的不连续公共子串的长度（包含c字符串） -hdu4681

计算a、b字符串的不连续公共子串的长度（包含c字符串） ----hdu4681

题意：

给你字符串A,B,C，让你找一个字符串D，使得D串是A,B的字串，C串是D的连续字串。

做法：

找出C串在A,B串的位置。

对于每一个位置对，D串的长度为前一半的最长公共子序列+C串的长度+后一半的最长公共子序列

#include <iostream>
#include <cstdio>
#include <cstring>
#define N 1005
#define Max(a,b) a>b?a:b
using namespace std;
int len1,len2,len3,num;
int dp1[N][N],dp2[N][N],pp[N<<2][2];
//dp1[][]表示字符串a，b从前往后的最大公共子串，dp2[][]表示字符串a，b从后往前的最大公共子串
//pp[][]记录字符串c在a，b中出现的第一个位置和最后一个位置
char a[N],b[N],c[N];
void solve(char *str,int n)
{
    int i,j,k;
    int l=strlen(str);
    for(i=0; i<=l-len3; i++)
        if(str[i]==c[0])
        {
            for(j=i,k=0; j<n&&k<len3; j++)
                if(str[j]==c[k])
                    k++;
            if(k==len3)
            {
                pp[num][0]=i+1;
                pp[num][1]=j;
                num++;
            }
            else break;
        }
}

int main()
{
    int i,j,T,Count=0;
    scanf("%d",&T);
    getchar();
    while(T--)
    {
        gets(a);
        len1=strlen(a);
        gets(b);
        len2=strlen(b);
        gets(c);
        len3=strlen(c);
        memset(dp1,0,sizeof(dp1));
        for(i=1; i<=len1; i++)
            for(j=1; j<=len2; j++)
                if(a[i-1]==b[j-1])dp1[i][j]=dp1[i-1][j-1]+1;
                else dp1[i][j]=Max(dp1[i-1][j],dp1[i][j-1]);

        memset(dp2,0,sizeof(dp2));
        for(i=len1; i>=1; i--)
            for(j=len2; j>=1; j--)
                if(a[i-1]==b[j-1])dp2[i][j]=dp2[i+1][j+1]+1;
                else dp2[i][j]=Max(dp2[i+1][j],dp2[i][j+1]);

        int x,y;
        num=0;
        solve(a,len1);
        x=num;
        solve(b,len2);
        y=num-x;

        int ans=0;
        for(i=0; i<x; i++)
            for(j=0; j<y; j++)
                ans=Max(ans,dp1[pp[i][0]-1][pp[x+j][0]-1]+dp2[pp[i][1]+1][pp[x+j][1]+1]);
        printf("Case #%d: %d\n",++Count,ans+len3);
    }
    return 0;
}