【CF873F】Forbidden Indices
题意：给你一个串s，其中一些位置是危险的。定义一个子串的出现次数为：它的所有出现位置中，不是危险位置的个数。求s的所有子串中，长度*出现次数的最大值。
|S|<=200000
题解：板子题啊，沿着pre树统计一下子树权值和，然后用mx*权值和更新答案就好了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=400010;
int n,tot,last;
long long ans;
char S[maxn],T[maxn];
int ch[maxn][26],pre[maxn],mx[maxn],r[maxn],st[maxn],tb[maxn];
inline void extend(int x)
{int p=last,np=++tot;mx[np]=mx[p]+1,last=np;for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=np;if(!p) pre[np]=1;else{int q=ch[p][x];if(mx[q]==mx[p]+1) pre[np]=q;else{int nq=++tot;mx[nq]=mx[p]+1,pre[nq]=pre[q],pre[np]=pre[q]=nq;memcpy(ch[nq],ch[q],sizeof(ch[q]));for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=nq;}}
}
int main()
{scanf("%d%s%s",&n,S,T);int i;last=tot=1;for(i=0;i<n;i++) extend(S[i]-'a'),r[last]='1'-T[i];for(i=1;i<=tot;i++) st[mx[i]]++;for(i=1;i<=tot;i++) st[i]+=st[i-1];for(i=tot;i>=1;i--) tb[st[mx[i]]--]=i;for(i=tot;i>=1;i--) r[pre[tb[i]]]+=r[tb[i]];for(i=1;i<=tot;i++) ans=max(ans,1ll*r[i]*mx[i]);printf("%I64d",ans);return 0;
}
