SAM 学习笔记

· · 个人记录

SAM 学习笔记

鲜花

那些生活在阴沟里的人却来指责阳光耀眼的人，还要试图用道德绑架你，而这种人却最没原则。

这个世界太浑浊了，有些人的恨没有原因的，因为他们平庸没有天赋，你的善良和才华都成了原罪。

我有好好做人的教养但也有不好惹的能力我的棍棒只会用来打那些得寸进尺的人。

——董宇辉

但是这并不属于我的世界啊。。。

生活有一种英雄主义，那就是认清了生活的真相，依然热爱生活。

——罗曼罗兰

SAM

设 Right(T) 集合表示在一个字符串 S 中，一个子串 T 的出现位置的右端点集合，后文中简记为 R(T)。

性质：

推论：R 集合形成树的结构，也就是后缀树。其中后缀树满足父亲节点代表的子串是儿子节点代表的子串的后缀。

进一步的：

$\text{Lemma 3.}$ 若有 $R(T_1)=R(T_k)$，并且 $|T_1|\leq |T_k|$，且 $T_1$ 是 $T_2$ 的后缀，$T_2$ 是 $|T_3|$ 的后缀 $……$ 依次类推。则 $R(T_1)=R(T_2)=\dots=R(T_k)$。

也就是说每一个节点对应的是一段长度在一定区间内的子串，并且依次存在后缀关系。

就是说 R(x)⊆R(y)，就说明 y 是 x 的后缀。

有限状态自动机 \text{DFA}：识别字符串

形如 (G,δ,\sum,x_0)，其中 G 表示一个有向图，δ:(x\in G,c\in \sum)→y\in G，x_0 表示当前所在的节点。

设 S=s_1s_2\dots s_{n-1}s_n，就会有下面这个流程：

然后如果直接这样建出有向图，点数和边数都是爆炸的。。。

考虑 R 集合相同的节点出边一定是相同的，考虑将 R 集合相同的后缀压缩成一个节点。

应用：求字符串 S 的两个子串 T_1,T_2 的 \text{LCS}

至于怎么建 SAM，直接背板子即可。。。

广义 SAM

简单来说就是按照 \text{BFS} 序对 Trie 建 SAM。

例题

luoguP6640 [BJOI2020] 封印

给出只包含小写字母 a,b 的两个字符串 s, t，q 次询问，每次询问 s[l \dots r] 和 t 的最长公共子串长度。

对于全部数据，满足 |s|,|t|\leq 2\times 10^5，q\leq 2\times 10^5。

Idea

对于每一个 i，可以维护一个最小的 lim_i 使得 s_{lim_i\dots i} 是 t 的子串。这一部分用 SAM 实现，对 t 建立 SAM 然后不断枚举下一个字符的即可。

然后令 len_i=i-lim_i+1。那么对于一个询问 [l,r]，相当于求 \max_{l\leq i\leq r} \{\min (len_i,i-l+1)\}。令 f_i=i-l+1，则 len_i-f_i=i-lim_i+1-(i-l+1)=l-lim_i 单调不增（lim_i 单调不降），二分即可。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 200010
int n,m,Q,len[N],lim[N];
char S[N],T[N];

int read ()
{
    int k=1,s=0;char ch=getchar ();
    while (!isdigit (ch)) {if (ch=='-') k=-1;ch=getchar ();}
    while (isdigit (ch)) {s=s*10+ch-'0';ch=getchar ();}
    return k*s;
}

struct NodeA
{
    int idx,from;
    struct NodeB
    {
        int son[2],fail,len;
    }Tree[N<<2];

    void Init ()
    {
        memset (Tree,0,sizeof (Tree));
        idx=1,from=1;
    }

    int Extand (int len)
    {
        Tree[++idx].len=len;
        return idx;
    }

    void Insert (int x)
    {
        int pre=from,now=Extand (Tree[pre].len+1);
        while (pre && !Tree[pre].son[x])
        {
            Tree[pre].son[x]=now;
            pre=Tree[pre].fail;
        }
        if (!pre) Tree[now].fail=1;
        else
        {
            int _pre=Tree[pre].son[x];
            if (Tree[_pre].len==Tree[pre].len+1)
                Tree[now].fail=_pre;
            else
            {
                int _now=Extand (Tree[pre].len+1);
                Tree[_now].fail=Tree[_pre].fail;
                for (int i=0;i<2;i++)
                    Tree[_now].son[i]=Tree[_pre].son[i];
                while (pre && Tree[pre].son[x]==_pre)
                {
                    Tree[pre].son[x]=_now;
                    pre=Tree[pre].fail;
                }
                Tree[_pre].fail=Tree[now].fail=_now;
            }
        }
        from=now;
    }

}SAM;

struct NodeC
{
    int n,lg[N],maxv[21][N];

    void Init (int m,int *a)
    {
        n=m;
        lg[0]=-1;
        for (int i=1;i<=n;i++)
        {
            lg[i]=lg[i>>1]+1;
            maxv[0][i]=a[i];
        }
        for (int k=1;k<=20;k++)
            for (int i=1;i+(1<<k)-1<=n;i++)
                maxv[k][i]=max (maxv[k-1][i],maxv[k-1][i+(1<<(k-1))]);
    }

    int Query (int l,int r)
    {
        int k=lg[r-l+1];
        return max (maxv[k][l],maxv[k][r-(1<<k)+1]);
    }

}ST;

void Init ()
{
    scanf ("%s %s",S+1,T+1);
    n=strlen (S+1),m=strlen (T+1);
}

void Work ()
{
    SAM.Init ();
    for (int i=1;i<=m;i++)
        SAM.Insert (T[i]-'a');
    int pre=1,_len=0;
    for (int i=1;i<=n;i++)
    {
        while (pre!=1 && !SAM.Tree[pre].son[S[i]-'a'])
        {
            pre=SAM.Tree[pre].fail;
            _len=SAM.Tree[pre].len;
        }
        if (SAM.Tree[pre].son[S[i]-'a'])
        {
            pre=SAM.Tree[pre].son[S[i]-'a'];
            _len++;
        }
        len[i]=_len,lim[i]=i-_len+1;
    }
    ST.Init (n,len);
    Q=read ();
    while (Q--)
    {
        int l=read (),r=read ();
        if (lim[l]>=l)
            printf ("%d\n",ST.Query (l,r));
        else if (lim[r]<=l)
            printf ("%d\n",r-l+1);
        else
        {
            int p=lower_bound (lim+l,lim+r+1,l)-lim;
            printf ("%d\n",max (p-l,ST.Query (p,r)));
        }
    }
}

signed main ()
{
    Init ();
    Work ();
    return 0;
}

luoguP6793 [SNOI2020] 字符串

有两个长度为 n 的由小写字母组成的字符串 a,b，取出他们所有长为 k 的子串（各有 n-k+1 个），这些子串分别组成集合 A,B。现在要修改 A 中的串，使得 A 和 B 完全相同。可以任意次选择修改 A 中一个串的一段后缀，花费为这段后缀的长度。总花费为每次修改花费之和，求总花费的最小值。

对于所有数据，1\le k\le n\le 1.5\times 10^5。