给两个串，a与b，长度1e5，最多可以在a中选出x段互不相交的连续子串，问能不能拼成b，x的范围最多为30。
解法：
可以想到dp，dp[i][j]表示 a 串前 j 个字符取 i 段，能匹配到 b 串的最大前缀。这个状态是通过贪心构造的。
转移的时候也是贪心转移，分为多一段和不要这个字符两种情况。
a) 多一段：dp[i+1][j+lcp(a[j],b[dp[i][j]])]=max(dp[i+1][j+lcp(a[j],b[dp[i][j]])],dp[i][j]+lcp(a[j],dp[i][j])); 因为如果要从a串的a[j]处, b串的b[dp[i][j]]处取一段相同子串，可以贪心地取最长的一段，其中lcp(a[j],dp[i][j]) 可以拿后缀数组或者哈希维护。
b) 不要当前字符：dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
#include <bits/stdc++.h> using namespace std; const int maxn=200005; string s,t,o; bool flag; int N,K,Rank[maxn],tmp[maxn],sa[maxn],lcp[maxn],n,m,x,st[20][maxn],dp[32][maxn]; inline bool compare_sa(int i,int j) { if (Rank[i]!=Rank[j]) return Rank[i]<Rank[j]; else { int ri=(i+K<=N)?Rank[i+K]:-1; int rj=(j+K<=N)?Rank[j+K]:-1; return ri<rj; } } inline void construct_sa(string S,int *sa) { N=S.length(); for (int i=0;i<=N;++i) { sa[i]=i; Rank[i]=i<N?S[i]:-1; } for (K=1;K<=N;K*=2) { sort(sa,sa+N+1,compare_sa); tmp[sa[0]]=0; for (int i=1;i<=N;++i) tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0); for (int i=0;i<=N;++i) Rank[i]=tmp[i]; } } inline void construct_lcp(string S,int *sa,int *lcp) { N=S.length(); int h=0; lcp[0]=0; for (int i=0;i<N;++i) { int j=sa[Rank[i]-1]; h=max(h-1,0); for (;j+h<N&&i+h<N;++h) if (S[j+h]!=S[i+h]) break; lcp[Rank[i]-1]=h; } } inline void construct_rmq(int *lcp,int n) { for (int i=0;i<n;++i) st[0][i]=lcp[i]; for (int i=1;i<20;++i) for (int j=0;j+(1<<i)-1<n;++j) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]); } inline int query_rmq(int i,int j) { int x=0; while ((1<<(x+1))<=j-i+1) ++x; return min(st[x][i],st[x][j-(1<<x)+1]); } void solve() { for (int i=0;i<=x;++i) for (int j=0;j<=n;++j) { if (dp[i][j]>=m) { puts("YES"); return; } int _lcp=query_rmq(min(Rank[j],Rank[dp[i][j]+n+1]),max(Rank[j],Rank[dp[i][j]+n+1])-1); dp[i+1][j+_lcp]=max(dp[i+1][j+_lcp],dp[i][j]+_lcp); dp[i][j+1]=max(dp[i][j+1],dp[i][j]); } puts("NO"); } int main() { cin>>n>>s>>m>>t>>x; o=s+'$'+t; construct_sa(o,sa); construct_lcp(o,sa,lcp); construct_rmq(lcp,o.length()+1); solve(); return 0; }