Description
有一个只包含小写字母，长度为$n$的字符串$S$。有一些字母是好的，剩下的是坏的。
定义一个子串$S_{l cdots r}$是好的，当且仅当这个子串包含不超过$k$个坏的字母。
求有多少个不同的满足以下要求的字符串$T$：
$T$作为$S$的子串出现过。
存在一个$T$出现的位置$[l,r]$，满足$S_{l cdots r}$是好的。
Solution
建出$S$的SAM
可以$O(n)$计算出每个前缀最长满足条件的后缀长度$len$
考虑如何枚举所有子串，可以枚举所有SAM上状态$p$，再枚举该状态上所有子串，这些子串的长度在$[minlen,maxlen]$上，并且它们的末尾是一致的
已知由它们末尾的位置最多能向前扩展的长度，那么符合条件的子串个数就是$[minlen,maxlen]$和$[1,len]$的交集
在parent树上DP，父节点取子节点的最大值
#include<iostream> #include<cstring> #include<vector> #include<cstdio> #include<cmath> using namespace std; int n,sum[100005],las=1,tot=1,maxx[200005],K,pos; long long ans; char s[100005],b[100005]; struct SAM{ int fa,len,ch[27]; }sam[200005]; vector<int>ve[200005]; inline int read(){ int f=1,w=0; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return f*w; } void insert(int c){ int p=las,np=las=++tot; sam[np].len=sam[p].len+1; for(;p&&!sam[p].ch[c];p=sam[p].fa)sam[p].ch[c]=np; if(!p)sam[np].fa=1; else{ int q=sam[p].ch[c]; if(sam[q].len==sam[p].len+1)sam[np].fa=q; else{ int nq=++tot; sam[nq]=sam[q],sam[nq].len=sam[p].len+1,sam[q].fa=sam[np].fa=nq; for(;p&&sam[p].ch[c]==q;p=sam[p].fa)sam[p].ch[c]=nq; } } } void dfs(int k){for(int i=0;i<ve[k].size();i++)dfs(ve[k][i]),maxx[k]=max(maxx[k],maxx[ve[k][i]]);} int main(){ scanf("%s%s",s+1,b+1),n=strlen(s+1),K=read(); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(b[i]=='0'),insert(s[i]-'a'); for(int i=1;i<=tot;i++)ve[sam[i].fa].push_back(i); int p=1; for(int i=1;i<=n;i++){ p=sam[p].ch[s[i]-'a']; while(sum[i]-sum[pos]>K)++pos; maxx[p]=max(maxx[p],i-pos); } dfs(1); for(int i=1;i<=tot;i++)ans+=max(0,min(maxx[i],sam[i].len)-sam[sam[i].fa].len); printf("%lld ",ans); return 0; }