一眼题目。

题目简述如下:

  • 任务一:支持询问当前本质不同的子串的个数
  • 任务二:支持插入

很显然后缀自动机可以解决胜任,正好今天刚学了后缀自动机,那么就将它定为练手题了。

插入是很简单的,至于询问本质不同的字串的个数,我们知道新插入一个节点 $now$ 对答案的贡献是: $ |max(now)| - |min(now)| + 1$ 。我们建后缀自动机的时候只保存了 $max(now)$ ,难道还要保存一个 $min(now)$ 吗?其实不需要,根据其性质可以得到:$|max(now)| - |max(fa[now])|$,直接计算即可。

注意数据范围较大,记得开 $longlong$ !

*注:文中的 $|S|$ 指的是字符串 $S$ 的长度。

#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

#define ll long long
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

const int N=2e5+2;
const int inf=1e9+9;

template<typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

struct SAM{
    ll ans;
    std::map<int,int> ch[N];
    int last,cnt,len[N],fa[N];
    inline void Insert(int c){
        int p=last,now=last=++cnt;
        len[now]=len[p]+1;
        while(p&&!ch[p][c])ch[p][c]=now,p=fa[p];
        if(!p)fa[now]=1;
        else{
            int q=ch[p][c];
            if(len[q]==len[p]+1)fa[now]=q;
            else{
                int copy=++cnt;
                len[copy]=len[p]+1,ch[copy]=ch[q];
                fa[copy]=fa[q],fa[q]=fa[now]=copy;
                while(p&&ch[p][c]==q)ch[p][c]=copy,p=fa[p];
            } 
        }
        ans+=len[now]-len[fa[now]];
        return;
    }
}sam;

int main(){
    int n;IN(n);
    sam.last=sam.cnt=1;
    for(int i=1;i<=n;++i){
        int c;IN(c);
        sam.Insert(c);
        printf("%lld\n",sam.ans);
    }
    return 0;
} 
最后修改:2019 年 05 月 30 日 03 : 24 PM