[冲刺国赛2022] 模拟赛15

子串

题目描述

定义 \(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]);
}