题目
题目描述
有一个只包含小写字母，长度为 $n$ 的字符串 $S$ 。有一些字母是好的，剩下的是坏的。
定义一个子串 $S_{l\ldots r}$ 是好的，当且仅当这个子串包含不超过 $k$ 个坏的字母。
求有多少个不同的满足以下要求的字符串 $T$ ：
- $T$ 作为 $S$ 的子串出现过。
- 存在一个 $T$ 出现的位置 $[l,r]$ ，满足 $S_{l\ldots r}$ 是好的。
输入格式
第一行有一个字符串 $S$ 。
第二行有一个字符串 $B$ 。若 $B_i=$='1' 则表示 $S_i$ 是好的，否则表示 $S_i$ 是坏的。
第三行有一个整数 $k$ 。
输出格式
一个整数：答案。
样例
样例一
input
ababab
010101
1
output
5
explanation
所有'b'是好的，'a'是坏的。
满足条件的字符串有："a","ab","b","ba","bab"。
样例二
input
ababab
100000
1
output
3
explanation
$S_1$ 是好的，其他的字符都是坏的。
满足条件的字符串有："a","ab","b"。
虽然 $S_{3\ldots4}=S_{5\ldots6}=$"ab" 是坏的，但是这并不影响 "ab" 满足条件，因为 $S_{1\ldots2}=$"ab" 是好的。
数据范围与提示
子任务 $1$（$10$10 分）：$n\leq 10$。
子任务 $2$（$10$10 分）：$n\leq 100$。
子任务 $3$（$10$10 分）：$n\leq 1000$。
子任务 $4$（$10$ 分）：$n\leq 100000,k=n$。
子任务 $5$（$10$ 分）：$n\leq 100000,k=0$。
子任务 $6$（$20$ 分）：$n\leq 100000$，若$S_i=S_j$，则$B_i=B_j$ 。
子任务 $7$（$30$30 分）：$n\leq 100000$。
对于 $100\%$ 的数据：$1\leq n\leq {10}^5,0\leq k\leq {10}^5$， $S$ 只包含小写字母。
题解
用$L_i$表示位置$i$最多能往前扩展多少字符，那么答案就是每个状态的$min(len_i,L_{endpos_x})-len_{fa_i},x\in right_i$
$L_i$可以用二分处理出来，维护每个状态的最大的$L_{endpos_x}$，这个用线段树合并记录一下就行了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl s[k].l
# define tr s[k].r
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=3e5+5;
struct p{
int x,l,r;
}s[MAX<<5];
int n,k,tot;
LL ans;
int rt[MAX],Len[MAX],sum[MAX];
char a[MAX],b[MAX];
void pus(int k) {s[k].x=max(s[tl].x,s[tr].x);}
void change(int l,int r,int &k,int x,int dis)
{
if(!k) k=++tot;
s[k].x=max(s[k].x,dis);
if(l==r) return;
if(x<=mid) change(l,mid,tl,x,dis);
else change(mid+1,r,tr,x,dis);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
int k=++tot;
return tl=merge(s[x].l,s[y].l),tr=merge(s[x].r,s[y].r),pus(k),k;
}
struct SAM{
int l,r,L;
int len[MAX],fa[MAX],id[MAX],tax[MAX],siz[MAX];
int son[MAX][26];
SAM() {l=r=1;}
void ins(int x,int id)
{
int tt=r;
len[r=++l]=++L,change(1,n,rt[r],id,Len[id]);
for(;tt&&!son[tt][x];tt=fa[tt])
son[tt][x]=r;
if(!tt) return void(fa[r]=1);
int qwq=son[tt][x];
if(len[qwq]==len[tt]+1) return void(fa[r]=qwq);
len[++l]=len[tt]+1,fa[l]=fa[qwq],fa[qwq]=fa[r]=l;
for(int i=0;i<26;++i)
son[l][i]=son[qwq][i];
for(int i=tt;son[i][x]==qwq;i=fa[i])
son[i][x]=l;
}
void Init()
{
for(int i=1;i<=l;++i)
++tax[len[i]];
for(int i=1;i<=n;++i)
tax[i]+=tax[i-1];
for(int i=l;i>=1;--i)
id[tax[len[i]]--]=i;
for(int i=l;i>=1;--i)
if(fa[id[i]]) ans+=max(0,min(len[id[i]],s[rt[id[i]]].x)-len[fa[id[i]]]),rt[fa[id[i]]]=merge(rt[fa[id[i]]],rt[id[i]]);
}
}_S;
int look(int r,int x)
{
int l=1,ans=r;
while(l<=r)
{
if(sum[mid]<=x+k) ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
int main()
{
scanf("%s%s%d",a+1,b+1,&k),n=strlen(a+1);
for(int i=n;i>=1;--i)
{
sum[i]=sum[i+1];
if(b[i]=='0') ++sum[i];
}
for(int i=1;i<=n;++i)
Len[i]=i-look(i,sum[i+1])+1;
for(int i=1;i<=n;++i)
_S.ins(a[i]-'a',i);
return _S.Init(),printf("%lld",ans),0;;
}
