HDU 4681 String (DP pretreatment + enumeration)

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

String

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1250 Accepted Submission(s): 455


Problem Description
Given 3 strings A, B, C, find the longest string D which satisfy the following rules:
a) D is the subsequence of A
b) D is the subsequence of B
c) C is the substring of D
Substring here means a consecutive subsequnce.
You need to output the length of D.


Input
The first line of the input contains an integer T(T = 20) which means the number of test cases.
For each test case, the first line only contains string A, the second line only contains string B, and the third only contains string C.
The length of each string will not exceed 1000, and string C should always be the subsequence of string A and string B.
All the letters in each string are in lowercase.



Output
For each test case, output Case #a: b. Here a means the number of case, and b means the length of D.


Sample Input
2
aaaaa
aaaa
aa
abcdef
acebdf
cf



Sample Output
Case #1: 4
Case #2: 3

Hint
For test one, D is "aaaa", and for test two, D is "acf".




Source
2013 Multi-University Training Contest 8




C.:
Given A, B, C three series. For one of the longest string D. The D is A, public B (string of not requiring continuous), and the C is a continuous D string.



Breakthrough: C on problem solving


Train of thought:

Meet the conditions of the D string is of the form x+ c+ Z; X C in front of A, B maximum consecutive substring, Y C behind the A, B maximum consecutive substring, then pretreatment of dp1[i][j] - A I B J position location in front, in front of the longest sequence, dp2[i][j] - A the I position behind, B J position behind the longest sequence, and then position the enumeration initials C in A, B, C in the pretreatment position respectively extend to the back of A, the position of B, then O (1) to update the ANS.


Code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 100005
#define mod 1000000007
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,m,ans;
int len1,len2,len3;
char a[maxn],b[maxn],c[maxn];
int dp1[maxn][maxn],dp2[maxn][maxn];
int last1[maxn],last2[maxn];
vector<int>v1,v2;

void presolve()
{
    int i,j,t;
    len1=strlen(a+1);
    len2=strlen(b+1);
    len3=strlen(c+1);
    memset(last1,0,sizeof(last1));
    memset(last2,0,sizeof(last2));
    memset(dp1,0,sizeof(dp1));
    memset(dp2,0,sizeof(dp2));
    v1.clear();
    for(i=1; i<=len1; i++)
    {
        if(a[i]==c[1])
        {
            v1.push_back(i);
            t=2;
            if(len3==1)
            {
                last1[i]=i;
                continue ;
            }
            for(j=i+1; j<=len1; j++)
            {
                if(a[j]==c[t])
                {
                    t++;
                    if(t>len3)
                    {
                        last1[i]=j;
                        break ;
                    }
                }
            }
        }
    }
    v2.clear();
    for(i=1; i<=len2; i++)
    {
        if(b[i]==c[1])
        {
            v2.push_back(i);
            t=2;
            if(len3==1)
            {
                last2[i]=i;
                continue ;
            }
            for(j=i+1; j<=len2; j++)
            {
                if(b[j]==c[t])
                {
                    t++;
                    if(t>len3)
                    {
                        last2[i]=j;
                        break ;
                    }
                }
            }
        }
    }
    for(i=1; i<=len1; i++)
    {
        for(j=1; j<=len2; j++)
        {
            if(a[i]==b[j]) dp1[i][j]=max(dp1[i][j],dp1[i-1][j-1]+1);
            else dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1]);
        }
    }
    for(i=len1; i>=1; i--)
    {
        for(j=len2; j>=1; j--)
        {
            if(a[i]==b[j]) dp2[i][j]=max(dp2[i][j],dp2[i+1][j+1]+1);
            else dp2[i][j]=max(dp2[i][j+1],dp2[i+1][j]);
        }
    }
}
void solve()
{
    int i,j,t,u,v;
    ans=0;
    for(i=0; i<v1.size(); i++)
    {
        for(j=0; j<v2.size(); j++)
        {
            u=v1[i];
            v=v2[j];
            if(last1[u]&&last2[v])
            {
                ans=max(ans,dp1[u-1][v-1]+dp2[last1[u]+1][last2[v]+1]+len3);
            }
        }
    }
}
int main()
{
    int i,j,t,test=0;
    scanf("%d",&t);
    for(i=1; i<=t; i++)
    {
        scanf("%s%s%s",a+1,b+1,c+1);
        presolve();
        solve();
        printf("Case #%d: %d\n",++test,ans);
    }
    return 0;
}
/*
2
acdbb
acdb
acd
cxxyxxjz
xyz
xz
*/











Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Austin at December 08, 2013 - 4:28 AM