hiho#1445 重复旋律5 求子串数量后缀自动机

古城微笑少年丶 2021-11-06 01:14 265阅读 0赞

[题目传送门][Link 1]

题意：给出一个字符串，求子串的个数。

思路：后缀自动机的题真是每做一题就更理解一些。

SAM中的每一状态$p$都代表了一种子串，而p包含的字符串的个数是$len\[p\]-len\[fa\[p\]\]$，所以答案就是$sigma len\[i\]-len\[fa\[i\]\]$，还有答案要开long long。

#include<bits/stdc++.h>
    #define clr(a,b) memset(a,b,sizeof(a))
    using namespace std;
    typedef long long ll;
    const int inf=0x3f3f3f3f;
    const int maxn=1000010;
    char s[maxn];
    int len[maxn<<1],ch[maxn<<1][27],fa[maxn<<1],tot=1,root=1,last=1,siz;
    void extend(int x){
        int now=++tot,pre=last;
        last=now,len[now]=len[pre]+1;
        while( pre && !ch[pre][x]){
            ch[pre][x]=now;
            pre=fa[pre];
        }
        if(!pre)fa[now]=root;
        else{
            int q = ch[pre][x];
            if(len[q]==len[pre]+1)fa[now]=q;
            else {
                int nows=++tot;
                memcpy(ch[nows],ch[q],sizeof(ch[q]));
                len[nows]=len[pre]+1;
                fa[nows]=fa[q];
                fa[q]=fa[now]=nows;
                while(pre&&ch[pre][x]==q){
                    ch[pre][x]=nows;
                    pre=fa[pre];
                }
            }
        }
    }
    
    int main(){
        scanf("%s",s);
        siz=strlen(s);
        for(int i=0;i<siz;i++)
        {
            int p=s[i]-'a';
            extend(p);
        }
        ll ans=0;
        for(int i=1;i<=tot;i++)
        {
            ans+=len[i]-len[fa[i]];
        }
        cout<<ans<<endl; 
    }

转载于:https://www.cnblogs.com/mountaink/p/10663140.html

[Link 1]: http://hihocoder.com/problemset/problem/1445?sid=1480953