LINK：[Lydsy1710月赛]小A的咒语
每次给定两个串 要求从a串中选出x段拼成B串 能否做到。T组数据。
\(n\leq 100000,m\leq 100000,T\leq 10,x\leq 100\)
首先考虑贪心的从前往后匹配 若果当前匹配位置比之前还要远覆盖之前的 但是这样做会出现问题。
可能当前匹配的是之前匹配的后面的一段 也可能是之前的一段。
所以需要dp来解决这个后效性问题 设g[i][j]表示前i段个字符选出了j段所能拼成B串的最大长度。
有g[i][j]=g[i-1][j] 考虑匹配的时候 从i+1 和g[i][j]+1进行匹配。
为什么要这样做考虑g数组值小一点显然当前大一点的g数组比小一点的要优 给后面带来的结果不会更差。
由于第二维状态的存在也解决了上述 到底是匹配之前的还是匹配之后的问题。
考虑转移 枚举K 进行转移 f[i+k][j+1]=f[i][j]+k; 考虑这里的k取到最大值的时候对后面结果不会更差。
注意这里只能采用刷表法 因为填表的话还是不知道K是多少。
多组数据 注意清空。
const int MAXN=400010;
int n,k,m,ww,L,R,w1,w2;
int x[MAXN],y[MAXN],sa[MAXN],rk[MAXN],h[MAXN],c[MAXN];
int f[MAXN][21],Log[MAXN],g[100010][103];
char a[MAXN];
inline void SA()
{
m=150;
rep(1,m,i)c[i]=0;
rep(1,n,i)++c[x[i]=a[i]];
rep(1,m,i)c[i]+=c[i-1];
rep(1,n,i)sa[c[x[i]]--]=i;
for(int k=1;k<=n;k=k<<1)
{
int num=0;
rep(n-k+1,n,i)y[++num]=i;
rep(1,n,i)if(sa[i]>k)y[++num]=sa[i]-k;
rep(1,m,i)c[i]=0;
rep(1,n,i)++c[x[i]];
rep(1,m,i)c[i]+=c[i-1];
fep(n,1,i)sa[c[x[y[i]]]--]=y[i];
rep(1,n,i)y[i]=x[i],x[i]=0;
x[sa[1]]=num=1;
rep(2,n,i)x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?num:++num;
if(n==num)break;
m=num;
}
rep(1,n,i)rk[sa[i]]=i;
}
inline void get_height()
{
int k=0;
rep(1,n,i)
{
if(rk[i]==1)continue;
if(k)--k;
int j=sa[rk[i]-1];
while(a[i+k]==a[j+k])++k;
h[rk[i]]=k;
}
rep(2,n,i)
{
f[i-1][0]=h[i];
Log[i]=Log[i>>1]+1;
}
rep(1,Log[n-1],j)
rep(1,n-1-(1<<j)+1,i)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline int LCP(int x,int y)
{
if(x>w1||y>w2)return 0;
x=rk[x];y=rk[y+w1+1];
if(x>y)swap(x,y);--y;
int z=Log[y-x+1];
return min(f[x][z],f[y-(1<<z)+1][z]);
}
int main()
{
freopen("1.in","r",stdin);
int T;get(T);
rep(2,300000,i)Log[i]=Log[i>>1]+1;
while(T--)
{
get(w1);get(w2);int get(cc);
gc(a);gc(a+w1+1);
a[w1+1]='z'+1;a[w1+w2+2]='z'+2;
n=w1+w2+1;
SA();get_height();
memset(g,0,sizeof(g));
rep(0,w1,i)
{
rep(0,cc,j)
{
if(i>=1)g[i][j]=max(g[i-1][j],g[i][j]);
int ww=LCP(i+1,g[i][j]+1);
if(i+ww<=w1)g[i+ww][j+1]=max(g[i][j]+ww,g[i+ww][j+1]);
//cout<<g[i+ww][j+1]<<endl;
}
}
if(g[w1][cc]>=w2){puts("YES");}
else puts("NO");
}
return 0;
}