形式化题意
给你两个串 \(s,t\)，需要用最少的 \(s\) 的子串拼接出 \(t\)，可重复使用。
思路
显然有一个贪心，从 \(t\) 的开头开始，每次尽可能长的匹配一段，直到将 \(t\) 匹配完成。
因为，如果放弃一个可以匹配的字符，让它参加到下一个子串的匹配，并不会使下次匹配的终点落在当前方案后面，这样在匹配次数相同的情况下，这种贪心的匹配长度最长。
然后，问题转化为，从 \(t\) 的某个字符开始，最长能与 \(s\) 的子串匹配多长。
这显然要用后缀数组。
考虑将 s+#+t 拼接在一起，处理出后缀数组和 h 数组。
对于 \(t\) 的每个位置，其与 \(s\) 子串匹配的最长方式一定是和 在 sa 数组中前或后第一个属于 s 的后缀 匹配。
前后扫两边 sa 数组，处理出 \(t\) 每个位置最长的匹配方式，直接贪心即可。
复杂度 \(O(n\log n)\) ，瓶颈为预处理后缀数组，当然用 sa-is 可以降到 \(O(n)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,inf=1e9;int read(){int ans=0;char c=getchar();bool f=0;for(;!isdigit(c);c=getchar())if(c=='-')f=1;for(;isdigit(c);c=getchar())ans=(ans<<=1)+(ans<<2)+(c^48);return f?-ans:ans;
}void print(int x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10|48);
}int n,m;
char s[N<<1];
int rk[N<<1],sa[N],id[N],cnt[N],oldrk[N<<1],h[N];void build(char *s,int n){int m=128;memset(cnt,0,(m+1)*sizeof(int));for(int i=1;i<=n;++i)cnt[rk[i]=s[i]]++;for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1];for(int i=n;i>=1;--i)sa[cnt[rk[i]]--]=i;for(int w=1,p,cur;w<n;w<<=1){cur=0;for(int i=n-w+1;i<=n;++i)id[++cur]=i;for(int i=1;i<=n;++i)if(sa[i]>w)id[++cur]=sa[i]-w;memset(cnt,0,(m+1)*sizeof(int));for(int i=1;i<=n;++i)cnt[rk[id[i]]]++;for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1];for(int i=n;i>=1;--i)sa[cnt[rk[id[i]]]--]=id[i];swap(rk,oldrk);p=0;for(int i=1;i<=n;++i){if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])rk[sa[i]]=p;else rk[sa[i]]=++p;}m=p;if(m==n)break;}for(int i=1,p=0;i<=n;++i){if(rk[i]==1)continue;if(p)p--;while(s[i+p]==s[sa[rk[i]-1]+p])++p;h[rk[i]]=p;}
}char gc(){char c=getchar();while(c<'A'||c>'Z')c=getchar();return c;
}int val[N];signed main(){n=read();m=read();int cnt=0;for(int i=1;i<=n;++i)s[++cnt]=gc();s[++cnt]='#';for(int i=1;i<=m;++i)s[++cnt]=gc();build(s,cnt);for(int i=1,p=0,v=inf;i<=cnt;++i){v=min(v,h[i]);if(sa[i]<=n){p=i,v=inf;}else if(sa[i]>n+1){if(p)val[sa[i]-n-1]=v;}}for(int i=cnt,p=0,v=inf;i>=1;--i){if(sa[i]<=n){p=i,v=inf;}else if(sa[i]>n+1){if(p)val[sa[i]-n-1]=max(val[sa[i]-n-1],v);}v=min(v,h[i]);}int ans=0,p=1;while(p<=m){++ans;p+=val[p];}print(ans);putchar('\n');return 0;
}