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.
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.
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: 3HintFor test one, D is "aaaa", and for test two, D is "acf".
Source
Recommend
zhuyuanchen520
/*
* Author: *******
* Created Time: 2013/8/15 19:16:58
* File Name: String.cpp
* solve: String.cpp
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define sz(v) ((int)(v).size())
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repf(i, a, b) for (int i = (a); i <= (b); ++i)
#define repd(i, a, b) for (int i = (a); i >= (b); --i)
#define clr(x) memset(x,0,sizeof(x))
#define clrs( x , y ) memset(x,y,sizeof(x))
#define out(x) printf(#x" %d\n", x)
#define sqr(x) ((x) * (x))
typedef long long LL;
const int INF = 1000000000;
const double eps = 1e-8;
const int maxn = 1100;
char A[maxn];
char B[maxn];
char C[maxn];
int f_dp[maxn][maxn];//前面LCS
int b_dp[maxn][maxn];//后面LCS
int lena,lenb,lenc;
int search_ca(int s)
{
int end = 0;
for(int i = s;i<lena;++i)
{
if(A[i] == C[end])
{
end++;
}
if(end == lenc)
{
return i;
}
}
return -1;
}
int search_cb(int s)
{
int end = 0;
for(int i = s;i<lenb;++i)
{
if(B[i] == C[end])
{
end++;
}
if(end == lenc)
return i;
}
return -1;
}
vector<int> s;
vector<int> e;
int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
int k = 1;
while(T--)
{
s.clear();
e.clear();
scanf("%s%s%s",A,B,C);
lena = strlen(A);
lenb = strlen(B);
lenc = strlen(C);
clr(f_dp);
clr(b_dp);
for(int i = 1;i<=lena;++i)
for(int j = 1;j<=lenb;++j)
{
f_dp[i][j] = max(f_dp[i-1][j],f_dp[i][j-1]);
if(A[i-1] == B[j-1])
{
f_dp[i][j] = f_dp[i-1][j-1] + 1;
}
}
for(int i = lena;i>=1;--i)
for(int j = lenb;j>=1;--j)
{
b_dp[i][j] = max(b_dp[i+1][j],b_dp[i][j+1]);
if(A[i - 1] == B[j - 1])
{
b_dp[i][j] = b_dp[i+1][j+1] + 1;
}
}
for(int i = 0;i<lena;++i)
{
if(A[i] == C[0])
{
int temp = search_ca(i);
if(temp != -1)
{
s.push_back(i);
e.push_back(temp);
}
}
}
int ans = -1;
for(int i = 0;i<lenb;++i)
{
if(B[i] == C[0])
{
int temp = search_cb(i);
if(temp != -1)
{
for(int j = 0;j<s.size();++j)
{
int sta = s[j];
int en = e[j];
ans = max(ans,f_dp[sta+1][i+1] + b_dp[en+1][temp+1]);
}
}
}
}
if(ans < 0)
ans = 0;
else
ans += lenc;
printf("Case #%d: %d\n",k++,ans-2);
}
return 0;
}