题目大意
给定两个长度不超过(400)的字符串(s)和(t),要求从(s)中选出两段不重叠的子序列连在一起,构造出字符串(t),问能否实现。
题解
设(Next[i][j])表示字符串(s)中在第(i)个位置之后字符(j)第一次出现的位置。去枚举(t)的前缀,假设(t)的前(x)个字符是第一个子序列,后(LenT-x)个字符是第二个子序列,那么有
(dp[i][j]=min(Next[dp[i-1][j]][t[i]],Next[dp[i][j-1]][t[j+x]]))
时间复杂度(O(N^3))。
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define RG register int
#define LL long long
char s[405],t[405];
int dp[402][402],Next[405][26];
int T,LenS,LenT;
inline bool DP(){
memset(Next,0x3f,sizeof(Next));
for(RG i=LenS;i>=1;--i){
for(RG j=0;j<26;++j)
Next[i-1][j]=Next[i][j];
Next[i-1][s[i]-'a']=i;
}
for(RG x=1;x<=LenT;++x){
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
bool flag=true;
for(RG i=0;i<=x;++i){
if(!flag) break;
for(RG j=0;j<=LenT-x;++j){
if(i>0) dp[i][j]=min(dp[i][j],Next[dp[i-1][j]][t[i]-'a']);
if(j>0) dp[i][j]=min(dp[i][j],Next[dp[i][j-1]][t[j+x]-'a']);
if(dp[i][j]>LenS){flag=false;break;}
}
}
if(dp[x][LenT-x]<=LenS) return true;
}
return false;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%s",s+1);
scanf("%s",t+1);
LenS=strlen(s+1);
LenT=strlen(t+1);
if(DP()) printf("YES
");
else printf("NO
");
}
return 0;
}