后缀自动机总结

学习笔记 题单

建议大家在观看本文之前观看这个HiHocoder的概念

其实SAM也没有什么难的.

考虑那个构建不就是每一次找一个长度-1的东西去搞.

如果没有的话就构造,然后更新父亲就好了.

那个maxlen串和minlen串的话就直接转移的时候+1就好了.

因为必然会有一个分水岭.

只可能小,不可能大.

代码实现

给出的是某谷模板的代码:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
    int f=1,sum=0;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return f*sum;
}
const int N=2000010;
char s[N];
int c[N],a[N],siz[N];
struct node{
    int ff,son[26],len;
}t[N<<1];
int last=1,tot=1;
void extend(int c){
    int p=last,np=++tot;last=np;
    t[np].len=t[p].len+1;
    while(p && !t[p].son[c])t[p].son[c]=np,p=t[p].ff;
    if(!p)t[np].ff=1;
    else{
        int q=t[p].son[c];
        if(t[p].len+1==t[q].len)t[np].ff=q;
        else{
            int nq=++tot;
            t[nq]=t[q];t[nq].len=t[p].len+1;
            t[q].ff=t[np].ff=nq;
            while(p && t[p].son[c]==q)t[p].son[c]=nq,p=t[p].ff;
        }
    }
    siz[np]=1;
}
int main()
{
    scanf("%s",s+1);int len=strlen(s+1);
    for(int i=1;i<=len;i++)extend(s[i]-'a');
    for(int i=1;i<=tot;i++)c[t[i].len]++;
    for(int i=1;i<=tot;i++)c[i]+=c[i-1];
    for(int i=1;i<=tot;i++)a[c[t[i].len]--]=i;
    ll ans=0;
    for(int i=tot;i;i--){
        int now=a[i];
        siz[t[now].ff]+=siz[now];
        if(siz[now]>1)ans=max(ans,1ll*t[now].len*siz[now]);
    }
    printf("%lld\n",ans);
    return 0;
}