【题意】给定长度为n和m的两个字符串S和T，要求在字符串S中取出若干段拼成T（可重复取），求最小段数，n,m<=50000。
【算法】后缀自动机 || 后缀数组
【题解】对串S建SAM，然后在上面尽可能地匹配T，匹配几次得到T就是答案。
#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; const int maxn=100010; struct tree{int len,fa,t[30];}t[maxn*2]; int tot,last,n,m,b[maxn]; void insert(int c){ int np=++tot; t[np].len=t[last].len+1; int x=last; while(x&&!t[x].t[c])t[x].t[c]=np,x=t[x].fa; last=np; if(!x)t[np].fa=1;else{ int y=t[x].t[c]; if(t[y].len==t[x].len+1)t[np].fa=y;else{ int nq=++tot; t[nq]=t[y]; t[nq].len=t[x].len+1; t[nq].fa=t[y].fa;t[y].fa=t[np].fa=nq; while(x&&t[x].t[c]==y)t[x].t[c]=nq,x=t[x].fa; } } } int main(){ scanf("%d%d",&n,&m); tot=last=1; for(int i=1;i<=n;i++){ char c=getchar(); while(c<'A'||c>'Z')c=getchar(); insert(c-'A'); } for(int i=1;i<=m;i++){ char c=getchar(); while(c<'A'||c>'Z')c=getchar(); b[i]=c-'A'; } int len=1,ans=0; while(len<=m){ int now=1; while(len<=m&&t[now].t[b[len]])now=t[now].t[b[len++]]; ans++; } printf("%d",ans); return 0; }