2015
09-17

# String

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.

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.

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.

2
aaaaa
aaaa
aa
abcdef
acebdf
cf

Case #1: 4
Case #2: 3

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


#include<iostream>
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
char sta[1001];
char stb[1001];
char stc[1001];
int lena,lenb,lenc;
int dp[1001][1001];
int dpf[1001][1001];
struct list
{
int x;
int y;
}node,n1,n2;
vector<list>vec[5];
void dps()
{
int i,j;
for(i=0;i<lena;i++)
if(sta[i]==stb[0])
for(i;i<lena;i++)dp[i][0]=1;
for(i=0;i<lenb;i++)
if(sta[0]==stb[i])
for(i;i<lenb;i++)dp[0][i]=1;
for(i=1;i<lena;i++)
{
for(j=1;j<lenb;j++)
{
if(sta[i]==stb[j])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
void dpfs()
{
int i,j;
for(i=lena-1;i>=0;i--)
if(sta[i]==stb[lenb-1])
for(i;i>=0;i--)dpf[i][lenb-1]=1;
for(i=lenb-1;i>=0;i--)
if(sta[lena-1]==stb[i])
for(i;i>=0;i--)dpf[lena-1][i]=1;
for(i=lena-2;i>=0;i--)
{
for(j=lenb-2;j>=0;j--)
{
if(sta[i]==stb[j])dpf[i][j]=dpf[i+1][j+1]+1;
else dpf[i][j]=max(dpf[i+1][j],dpf[i][j+1]);
}
}
}
void init()
{
memset(dp,0,sizeof(dp));
memset(dpf,0,sizeof(dpf));
vec[0].clear();
vec[1].clear();
gets(sta);
gets(stb);
gets(stc);
lena=strlen(sta);
lenb=strlen(stb);
lenc=strlen(stc);
}
void sear(char str[],int pos)
{
int lens=strlen(str);
int i,j,k;
for(i=0;i<lens;i++)
{
if(str[i]==stc[0])
{
for(k=0,j=i;j<lens;j++)
{
if(str[j]==stc[k])k++;
if(k==lenc)break;
}
if(j<lens)
{
node.x=i;
node.y=j;
vec[pos].push_back(node);
//  cout<<pos<<" "<<i<<" "<<j<<endl;
}
}
}
}
void prin(int cas)
{
int l1=vec[0].size();
int l2=vec[1].size();
int maxx=0;
int i,j;
for(i=0;i<l1;i++)
{
for(j=0;j<l2;j++)
{
n1=vec[0][i];
n2=vec[1][j];
int c1,c2;
c1=c2=0;
if(n1.x-1>=0&&n2.x-1>=0)c1=dp[n1.x-1][n2.x-1];
if(n1.y+1<lena&&n2.y+1<lenb)c2=dpf[n1.y+1][n2.y+1];
maxx=max(maxx,c1+c2+lenc);
//  printf("%d,%d--%d,%d--%d--%d\n",n1.x,n1.y,n2.x,n2.y,c1,c2);
}
}
printf("Case #%d: %d\n",cas,maxx);
}
int main()
{
int T,t;
//freopen("data.in","r",stdin);
scanf("%d%*c",&T);
for(t=1;t<=T;t++)
{
init();
dps();
dpfs();
sear(sta,0);
sear(stb,1);
prin(t);
}
return 0;
}