SAM个人向笔记

总

这是个人向笔记的第一篇。

个人向笔记主要为了自己看懂，初学的读者建议看 OI Wiki。

当然，遇到和我相同的困惑点可以阅读。

我学习的时候遇到的困难无非正确性和复杂度证明。

状态数和转移数的证明倒是很简单，OI Wiki 也讲得相对详细。

正确性证明

设 $S$ 为一个字符串， $c$ 为任意一个字符。

代表 $S$ 的点和代表 $Sc$ 的点之间一定有边。
$S$ 的 $c$ 出边的点对应的字符串一定以 $Sc$ 作为后缀
初始节点到每个点的路径集合就是这个点的字符串区间集合
现在的所有点就是 parent tree 中的所有点

正确性的证明只要盯着这些个结论证就可以了，具体方法就是一步步对照构建方法是否能维护这些性质，而有这些性质 SAM 的合法性是显然的。

复杂度证明

其他都可以看 wiki，但是复杂度中没有新建边或点的那一部分的证明，wiki 上写得极为简略。

记号见图（图中为 aaba 加上 b 后的结果，显然为 case3，注意 $dep_{lt}$ 就是上一次的 $dep_u$ ）：

SAM example

设 $dep$ 为深度数组， $len$ 为节点最长字符串，定义 u->v 为主要边当且仅当 $len_v=len_u+1$ 。

考虑 $dep_u$ 的值，显然 case12 都不会提高 $dep_u$ 。

先证明对于主要边 a->b， $dep_b=dep_a-k+1$ 其中 $k$ 为 $a$ 到树根的树上路径到 $b$ 到树根的树上路径的次要边条数，这是显然的，因为 $b$ 链除了根节点以外去掉最后一个字符的点一对应是 $a$ 链上两两不同的点（因为 $b$ 链本来就两两不同，又与 $a$ 链上那些点通过主要边相连）。

然后显然 $dep_p<dep_{lt}$ ，而 $dep_u=dep_r+1=dep_p-k+2\leqslant dep_p+2\leqslant dep_{lt}+1$ 而除了第一次外每一次跳都是次要边，不等式中 $k$ 的下限会提高 $1$ ，导致上界减小 $1$ ，所以此时最坏的上界为 $dep_{lt}+2-（\texttt{跳的次数}）$ 。

所以可以等同看作最坏情况下 $dep_u$ 的“提高”为 $O(n)$ 级别，而 $dep_u\geqslant 0$ 恒成立，所以 $dep_u$ 的降低次数也最多为 $O(n)$ 级别，而每次向上跳必然降低 $dep_u$ ，所以向上跳最坏 $O(n)$ 。

CODE

板子题代码。

注意节点编号从1开始。

#include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;++i)
#define frd(i,j,k) for(int i=j;i>=k;--i)
#define pc(x) putchar(x)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
using namespace std;using ll = long long;
namespace ugi{
char c=' ';
int in(void)
{
    int x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
}
using ugi::in;
const int maxn=(int)(4e6+12);
char str[maxn];
int n,cnt,lt,len[maxn],fa[maxn],ch[26][maxn],sl[maxn];
ll ans;
namespace tree{
struct edg
{
    int next,to;
}edge[maxn];
int cnt=1,head[maxn];
void intree(int a,int b)
{
    edge[cnt]=(edg){head[a],b};
    head[a]=cnt++;
}
void dfs(int dc)
{
    int v;
    for(int j=head[dc];j;j=edge[j].next)
    {
        dfs(v=edge[j].to);
        sl[dc]+=sl[v];
    }
    if(sl[dc]^1)
    {
        ans=max(ans,(ll)len[dc]*sl[dc]);
        // cout<<dc<<' '<<len[dc]<<' '<<sl[dc]<<endl;
    }
}
}
using tree::intree;using tree::dfs;
void insam(int c)
{
    int u=++cnt,tp=lt;
    len[u]=len[lt]+1;
    while(tp&&!ch[c][tp])
    {
        ch[c][tp]=u;
        // cout<<tp<<'-'<<c<<"->"<<u<<endl;
        tp=fa[tp];
    }
    if(!tp)
    {
        // cout<<"case1 ";
        fa[u]=1;
    }
    else
    {
        int q=ch[c][tp];
        if(len[q]==len[tp]+1)
        {
            // cout<<"case2 ";
            fa[u]=q;
        }
        else
        {
            // cout<<"case3 ";
            int r=++cnt;
            len[r]=len[tp]+1;fru(i,0,25)ch[i][r]=ch[i][q];
            for(;tp&&ch[c][tp]==q;tp=fa[tp])ch[c][tp]=r;
            fa[r]=fa[q];fa[q]=r;
            fa[u]=r;
        }
    }
    ++sl[u];
    lt=u;
}
int main()
{
    // fio();
    scanf("%s",str+1);
    n=strlen(str+1);
    lt=cnt=1;fru(i,1,n)insam(str[i]-'a');
    // cout<<endl;
    fru(i,2,cnt)
    {
        // cout<<i<<' '<<fa[i]<<endl;
        // fru(j,0,2)cout<<ch[j][i]<<':';
        // cout<<endl;
        intree(fa[i],i);
    }
    // cout<<endl;
    dfs(1);
    printf("%lld",ans);
    return 0; 
}