给定两个字符串S和T。你可以把S分成若干段，从左到右从1开始编号。现在要从你分出来的段中取出不超过x段，按编号从小到大依次拼接成字符串T。问是否有可行解。
1≤|T|≤|S|≤100000 x≤30
考虑DP。设f[i][j]表示用了S的前i个字符，取出了j段，最大能得到T的前多少个字符。 转移分两种情况： 1. f[i][j]—>f[i+1][j] 表示字符i+1单独成段且没被选 2. f[i][j]—>f[i+lcp][j+1] 其中lcp是S的后缀i+1和T的后缀f[i][j]+1的lcp。这里表示这一段lcp被选中。很显然取lcp的长度比取小于lcp的长度要更优。
最终复杂度就取决于如何求lcp了。设字符串总长为N，如果用后缀数组加rmq可以做到O(NlogN)预处理+O(1)查询。不过时限较大，可以用hash+二分，时间复杂度为O(NxlogN)
#include <cstdio> #include <cstring> #include <algorithm> #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) using namespace std; const int N=100005,M=31,mo[2]={998244353,1004535809},INF=1e9; typedef long long LL; int n,m,K,h1[2][N],h2[2][N],p[2][N],f[N][M]; char s[N],t[N]; bool Same(int x,int y,int l) { for (int i=0;i<2;i++) { if ((mo[i]+(h1[i][x+l-1]-(LL)h1[i][x-1]*p[i][l])%mo[i])%mo[i]!=(mo[i]+(h2[i][y+l-1]-(LL)h2[i][y-1]*p[i][l])%mo[i])%mo[i]) return 0; } return 1; } int getlcp(int x,int y) { int l,r,mid; for (l=0,r=min(n-x+1,m-y+1),mid=r>>1;l<r;mid=l+r>>1) if (!Same(x,y,mid)) r=mid;else l=mid+1; if (!Same(x,y,l)) l--; return l; } int main() { scanf("%d%s%d%s%d",&n,s+1,&m,t+1,&K); for (int j=0;j<2;j++) { p[j][0]=1; for (int i=1;i<N;i++) p[j][i]=(LL)p[j][i-1]*26%mo[j]; for (int i=1;i<=n;i++) h1[j][i]=((LL)h1[j][i-1]*26+s[i]-'a')%mo[j]; for (int i=1;i<=m;i++) h2[j][i]=((LL)h2[j][i-1]*26+t[i]-'a')%mo[j]; } f[0][0]=0; for (int i=0;i<n;i++) { for (int j=0;j<K;j++) if (f[i][j]<m) { int k=f[i][j],lcp=getlcp(i+1,k+1); f[i+1][j]=max(f[i+1][j],k); if (lcp>0) f[i+lcp][j+1]=max(f[i+lcp][j+1],k+lcp); } } for (int i=1;i<=n;i++) for (int j=1;j<=K;j++) if (f[i][j]==m) { printf("YES\n"); return 0; } printf("NO\n"); return 0; }