子串
题目描述
定义 \(cnt(s,t)\) 表示 \(t\) 在 \(s\) 中的出现次数。对于字符串 \(s\),定义一个子串 \(t\) 是重要的,当且仅当对于任意以 \(t\) 为子串的 \(t'\),都满足 \(cnt(s,t')<cnt(s,t)\)
给定串 \(S\),对于 \(S\) 的每个前缀求出,把这个前缀当成 \(s\) 时,重要串有多少个。
\(|S|\leq 10^6\),字符集 0~9
解法
考虑判断条件可以转化成:在 \(t\) 的前面或者后面加一个字符得到 \(t'\),\(t'\) 的出现次数不能等于 \(t\)
如果只考虑在前面加入字符,那么答案就是后缀自动机的节点数,可以在构建后缀自动机的时候得到个数。
再考虑在后面加入字符,如果某种节点的转移边只有一种的话,走这条转移边所得的 \(t'\) 出现次数会等于 \(t\),但是对于存在下一个字符为空的串 \(t\) 一定是重要的,这是一种不符合上面条件的特殊情况。
所以我们维护转移边出度为 \(1\) 的点数,用 \(\tt dfn\) 序和树状数组来维护链,就可以计算答案,时间复杂度 \(O(n\log n)\)
#include <bits/stdc++.h>
using namespace std;
const int M = 2000005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,cnt,last,Ind,res,b[M],ans[M];
int dfn[M],siz[M],out[M];char s[M];
vector<int> g[M];vector<pair<int,int>> v[M];
struct node{int ch[10],fa,len;}a[M<<1];
void add(int id,int c)
{
int p=last,np=last=++cnt;
a[np].len=a[p].len+1;
for(;p && !a[p].ch[c];p=a[p].fa)
{
a[p].ch[c]=np;out[p]++;
v[id].push_back(make_pair(p,1));
}
if(!p) a[np].fa=1;
else
{
int q=a[p].ch[c];
if(a[p].len+1==a[q].len) a[np].fa=q;
else
{
int nq=++cnt;a[nq]=a[q];
a[nq].len=a[p].len+1;out[nq]=out[q];
v[id].push_back(make_pair(nq,out[nq]));
a[np].fa=a[q].fa=nq;
for(;p && a[p].ch[c]==q;p=a[p].fa)
a[p].ch[c]=nq;
}
}
}
void dfs(int u)
{
dfn[u]=++Ind;siz[u]=1;
for(int v:g[u])
dfs(v),siz[u]+=siz[v];
}
//
void ins(int x,int c)
{
for(int i=x;i<=cnt;i+=i&(-i))
b[i]+=c;
}
int ask(int x)
{
int r=0;
for(int i=x;i>0;i-=i&(-i))
r+=b[i];
return r;
}
void Ins(int l,int r,int c)
{
ins(l,c);ins(r+1,-c);
}
void upd(int x,int y)
{
if(out[x]==1)
Ins(dfn[x],dfn[x]+siz[x]-1,-1),res--;
out[x]+=y;
if(out[x]==1)
Ins(dfn[x],dfn[x]+siz[x]-1,1),res++;
}
signed main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
n=read();scanf("%s",s+1);
last=cnt=1;
for(int i=1;i<=n;i++)
add(i,s[i]-'0'),ans[i]=cnt-1;
for(int i=2;i<=cnt;i++)
g[a[i].fa].push_back(i);
dfs(1);
for(int i=1;i<=cnt;i++) out[i]=0;
for(int i=1,p=1;i<=n;i++)
{
p=a[p].ch[s[i]-'0'];
for(auto x:v[i])
upd(x.first,x.second);
ans[i]+=ask(dfn[p])-res;
}
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
}
标签:字符,cnt,15,int,国赛,Ins,dfn,2022,out
From: https://www.cnblogs.com/C202044zxy/p/16585613.html