题解 P4070 【[SDOI2016]生成魔咒】

ubsan · 2020-07-21 14:06:17 · 题解

题意:

• 给你一个序列，动态加入数，在每一次加入后求本质不同的字串个数

题解：

如果会用 SAM 做上边提到的那道题，那这道题就简单了，因为 SAM 本来就是在线算法，直接输出答案即可。

如何求本质不同的字串个数

考虑 SAM 的 Right 集合所对应的子串包括原串所有本质不同的子串，而且由于 Sam 的性质 Min(x) 和 Max(x)之间是没有交集的，所有我们可以直接求 \sum Max(x) - Min(x) +1即可。

code:

//
// Created by swift on 2020/7/21.
//

#include<bits/stdc++.h>
#define int long long
using namespace std;
int len;
struct SAM{
    struct node{
        unordered_map<int,int>go;
        int fail,val,ans;
    }a[400000];
    int cnt=1,last=1;
    int tmp[400000];
    int id[400000];
    int ans;
    int solve(){
        return ans;
    }
    void add(int x){
        int p=last;
        int np=++cnt;
        a[np].val=a[p].val+1;
        a[np].ans=1;
        last=np;
        while(p&&a[p].go[x]==0){
            a[p].go[x]=np;
            p=a[p].fail;
        }
        if(!p){a[np].fail=1;ans+=a[np].val-a[a[np].fail].val;return;}
        int q=a[p].go[x];
        if(a[q].val==a[p].val+1){
            a[np].fail=q;
            ans+=a[np].val-a[a[np].fail].val;
            return;
        }
        int nq=++cnt;
        a[nq].val=a[p].val+1;
        a[nq].go=a[q].go;
        a[nq].fail=a[q].fail;
        a[q].fail=nq;
        a[np].fail=nq;
        while(p&&a[p].go[x]==q){
            a[p].go[x]=nq;
            p=a[p].fail;
        }
        ans+=a[np].val-a[a[np].fail].val;//求和
    }
}sam;
signed main(){
    scanf("%lld",&len);
    for(int i=0;i<len;i++){
        int a;
        scanf("%lld",&a);
        sam.add(a);
        printf("%lld\n",sam.solve());
    }
    return 0;
}