给出 $A$ 串和 $B$ 串，从 $A$ 串中选出至多 $x$ 个互不重合的段，使得它们按照原顺序拼接后能够得到 $B$ 串。求是否可行。多组数据。
$T\le 10$ ，$|A|,|B|\le 10^5$ ，$x\le 100$ 。
题解
后缀数组+倍增RMQ+贪心+dp
设 $f[i][j]$ 表示从 $A$ 串的前 $i$ 个字符中选出 $j$ 段，能够拼出 $B$ 串的最大长度。
那么考虑转移，如果 $i+1$ 不用则 $f[i+1][j]\leftarrow f[i][j]$ ，否则枚举拼的长度 $k$ ，如果 $A_{i+1...i+k}=B_{f[i][j]+1...f[i][j]+k}$ 则 $f[i+k][j+1]\leftarrow f[i][j]+k$ 。
仔细想想后一步可以不用这样处理，可以直接贪心地选择LCP来拼接。因为选择LCP相比不选择，多拼接的一段和前面相连，相当于本身没有占用次数，不会存在更优解。
因此使用后缀数组+倍增RMQ维护LCP，设 $LCP(A_{i+1},B_{f[i][j]+1})=t$ ，则有转移 $f[i+t][j+1]\leftarrow f[i][j]+t$ 。
时间复杂度 $O(T(nx+n\log n))$ 。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200010
using namespace std;
int sa[N] , r[N] , ws[N] , wa[N] , wb[N] , rank[N] , height[N] , mn[N][20] , log[N] , f[N][110];
char A[N] , B[N];
void init(int n , int m)
{
int i , j , p , *x = wa , *y = wb;
for(i = 0 ; i < m ; i ++ ) ws[i] = 0;
for(i = 0 ; i < n ; i ++ ) ws[x[i] = r[i]] ++ ;
for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1];
for(i = n - 1 ; ~i ; i -- ) sa[--ws[x[i]]] = i;
for(p = j = 1 ; p < n ; j <<= 1 , m = p)
{
for(p = 0 , i = n - j ; i < n ; i ++ ) y[p ++ ] = i;
for(i = 0 ; i < n ; i ++ ) if(sa[i] - j >= 0) y[p ++ ] = sa[i] - j;
for(i = 0 ; i < m ; i ++ ) ws[i] = 0;
for(i = 0 ; i < n ; i ++ ) ws[x[y[i]]] ++ ;
for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1];
for(i = n - 1 ; ~i ; i -- ) sa[--ws[x[y[i]]]] = y[i];
for(swap(x , y) , x[sa[0]] = 0 , p = i = 1 ; i < n ; i ++ )
{
if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]) x[sa[i]] = p - 1;
else x[sa[i]] = p ++ ;
}
}
for(i = 0 ; i < n ; i ++ ) rank[sa[i]] = i;
for(p = i = 0 ; i < n - 1 ; height[rank[i ++ ]] = p)
for(p ? p -- : 0 , j = sa[rank[i] - 1] ; r[i + p] == r[j + p] ; p ++ );
for(i = 1 ; i <= n ; i ++ ) mn[i][0] = height[i];
for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1;
for(i = 1 ; (1 << i) <= n ; i ++ )
for(j = 1 ; j + (1 << i) + 1 <= n ; j ++ )
mn[j][i] = min(mn[j][i - 1] , mn[j + (1 << (i - 1))][i - 1]);
}
inline int lcp(int p , int q)
{
p = rank[p] , q = rank[q];
if(p > q) swap(p , q);
p ++ ;
int k = log[q - p + 1];
return min(mn[p][k] , mn[q - (1 << k) + 1][k]);
}
int main()
{
int T;
scanf("%d" , &T);
while(T -- )
{
int n , m , k , i , j , t;
scanf("%d%d%d%s%s" , &n , &m , &k , A , B);
for(i = 0 ; i < n ; i ++ ) r[i] = A[i] - 'a' + 1;
for(i = 0 ; i < m ; i ++ ) r[i + n + 1] = B[i] - 'a' + 1;
r[n] = 27 , r[n + m + 1] = 0 , init(n + m + 2 , 28);
memset(f , 0 , sizeof(f));
for(i = 0 ; i < n ; i ++ )
for(j = 0 ; j <= k ; j ++ )
f[i + 1][j] = max(f[i + 1][j] , f[i][j]) , t = lcp(i , f[i][j] + n + 1) , f[i + t][j + 1] = max(f[i + t][j + 1] , f[i][j] + t);
for(i = 1 ; i <= k ; i ++ )
if(f[n][i] == m)
break;
if(i <= k) puts("YES");
else puts("NO");
}
return 0;
}