标签：Node SAM idx int link Parent 浅析

浅析SAM

目录

• 浅析SAM
  • 更好的阅读体验戳此进入
  • 写在前面
  • 一些事实
  • 相同子串个数
  • 例题 #1 LG-P3804 【模板】后缀自动机 (SAM)
  • 定长子串可重复字典序排序
  • 例题 #2 [ABC272F] Two Strings
    • 题面
    • Solution
    • Code
  • UPD

更好的阅读体验戳此进入

还没写完，春测之后有机会继续写。

写在前面

虽然是浅析 SAM 但是对于 SAM 的基础以及各种证明这里就不再叙述了，网上找到的如下 Blog 已经十分详尽了。

史上最通俗的后缀自动机详解。

或者直接看 OI-Wiki 也行。

主要是说一下一些常见套路以及各种例题。

一些事实

SAM 是一个 DAG，点数约 $ 2n $，边数约 $ 4n $。

在 SAM 的 DAG 上走一条边可以认为是在后缀追加一个字符。

通过 link 的反向边可以建立 Parent Tree，在 Parent Tree 向下走一个点可以认为是在其前插入一些字符。

相同子串个数

构建 SAM，构建 Parent Tree，显然每一个非分裂的节点都会代表一个结束的位置，所以对非分裂节点记一下 $ siz = 1 $，然后在 Parent Tree 上树形 DP 合并子树 $ siz $ 即可。

例题 #1 LG-P3804 【模板】后缀自动机 (SAM)

就是刚才说的问题的模板，就不细说了。

定长子串可重复字典序排序

见例题 #2。

例题 #2 [ABC272F] Two Strings

题面

给定两字符串 $ S, T $，求两字符串及其分别循环同构的所有字符串按字典序排序后顺序对个数，定义顺序对为 $ S $ 循环同构的字符串小于等于 $ T $ 循环同构的字符串的对数。

Solution

二分哈希，SA，SAM。

首先经典套路，对于循环同构直接断环然后倍长，以此其长度为 $ n $ 的子串可以表示所有循环同构的串，于是想到对于本题，倍长 $ S, T $，按照 S + S + T + T 的顺序排一下，此时对于其中起始点为 $ [1, n] \cup [2n + 1, 3n] $，长度为 $ n $ 的所有子串进行字典序排序然后求顺序对即可。

上述排序过程显然可以哈希之后，二分判断，复杂度大概是 $ O(n \log^2 n) $，但是这样不够优秀，显然也可以用 SA 求解，但是我不想写 SA，于是我们考虑强行使用 SAM 解决。

这个做法常数较大且细节较多，需要对 SAM 有一定的理解，建议先尝试用 SAM 写一下后缀排序后再考虑这道题。

再次思考一下我们的问题，显然可以转换为对原串的所有定长（即长度为 $ n $）子串之间可重复地排序。

不考虑可重复，不考虑复杂度，一个显而易见的思路就是我们顺序插入建出 SAM，显然在 SAM 中每走一步就会使长度 $ +1 $，且 SAM 可以表示出原串的任意子串，于是我们在 SAM（具体来说就是 SAM 的 DAG）上 dfs，然后贪心地优先走字典序较小的 trans，这样当深度（或者说步数）达到 $ n $ 的时候，我们直接将这个点对应的插入的位置 $ idx $ 存下来，这个存储的顺序就是对应终止于 $ idx $ 长度为 $ n $ 的字符串之间的字典序顺序关系。

现在让我们依次解决这些问题。

首先对于重复的问题，终止节点，或者说就是 $ endpos $ 不同的相同串，我们应该均保留，而上述过程中显然我们对于一个 $ endpos $ 的等价类中只保留了一个，而这个也很好处理，我们只需要对于找到的节点，遍历其在 Parent Tree 上的整个子树保留整棵子树上的所有 $ idx $ 即可。

然后考虑复杂度，一般来讲树上的搜索是可控的，而 DAG 上的搜索则不同，甚至是指数级的，于是我们想到尝试将这个过程从 SAM 上搜索转为从 Parent Tree 上搜索，这一部分的思路与 SAM 求 SA 较为相似，首先思考 SAM 与 Parent Tree 的区别，SAM 中的边是在尾部追加字符，而 Parent Tree 则是在前面插入字符。我们考虑将原串倒序插入 SAM，这样在 Parent Tree 中向更深走的时候意义就会变为追加后缀，而每个等价类中又代表着连续长度的子串，那么当我们在 Parent Tree 搜索时若 $ len \ge n $，则说明当前所在的 $ endpos $ 等价类中子串长度刚好会包括 $ n $，于是再次搜索这个点的子树并保留即可。

接下来不难发现这样是不存在贪心的，也就是说此过程是无序的，而 link 并不像 trans 一样本身带有字符，而对于这里的处理又要考虑到 SAM 中 Parent Tree 的本质，即在 SAM 中进行压缩，换句话说就是对于一个 $ v \rightarrow u $ 的 link，Parent Tree 中 $ u $ 为 $ v $ 的子节点，那么应该满足 $ u $ 追加若干长度后达到 $ v $，而此时我们的贪心就需要考虑到从 $ u $ 到 $ v $ 的过程中的 $ u $ 之后的第一个字符的字典序关系，这个是显然的，且若第一个字符相同那么一定不会被分裂成两个点，所以我们依次为依据，想到 $ u $ 是 $ v $ 的前缀，那么从 $ v $ 的初始位置（注意这里反向插入原串后 $ endpos $ 或者说代码中的 $ idx $ 的意义改为子串初始位置）位移 $ u $ 的长度后以原串中的对应位置的字符为关键字进行偏序地贪心即可。具体来说，Parent Tree 每条边的边权应为 p->idx + p->link->len。

下一个细节，对于建 SAM 时分裂出来的点，从意义上来讲其 $ idx $ 应该为对应次插入时的 $ idx $，且我们在记录答案时对于分裂出的点应该忽略。

再一个细节就是我们在搜索子树的时候不能直接返回一个 basic_string 等容器，否则会因递归多次导致复杂度退化。

而最终统计答案时，我们只需要保留所有范围在 $ [1, n] \cup [2n + 1, 3n] $ 的答案并记录即可。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define d(c) (c - 'a')

template < typename T = int >
inline T read(void);

struct Edge;
struct Node{
    unordered_map < int, Node* > trans;
    Node* link;
    int len;
    int idx;
    bool flag;
    Edge* head;
    int val;
    OPNEW;
}nd[2100000];
ROPNEW_NODE;
Node* root;

struct Edge{
    Edge* nxt;
    Node* to;
    int val;
    OPNEW;
}ed[4100000];
ROPNEW;

int N;
string S, T;
string base;
basic_string < bool > sorted;
basic_string < int > ret;

void Insert(int c, int idx){
    static Node* lst = root;
    Node* p = lst; Node* cp = lst = new Node; cp->idx = idx; cp->flag = true;
    cp->len = p->len + 1;
    while(p && !p->trans[c])p->trans[c] = cp, p = p->link;
    if(!p)cp->link = root;
    else if(p->trans[c]->len == p->len + 1)cp->link = p->trans[c];
    else{
        auto q = p->trans[c], sq = new Node(*q); sq->idx = idx; sq->flag = false;
        sq->len = p->len + 1;
        cp->link = q->link = sq;
        while(p && p->trans[c] == q)p->trans[c] = sq, p = p->link;
    }
}
void Link(void){
    auto endp = new Node();
    for(auto p = nd; p != endp;++p)
        if(p->link)
            p->link->head = new Edge{p->link->head, p, base.at(p->idx + p->link->len)};
}
void dfs_subt(Node* p){
    if(p->flag && ((1 <= p->idx && p->idx <= N) || (N * 2 + 1 <= p->idx && p->idx <= N * 3)))ret += p->idx;
    for(auto i = p->head; i; i = i->nxt)dfs_subt(SON);
}
void dfs(Node* p = root){
    if(N <= p->len){
        ret.clear();
        dfs_subt(p);
        int cnt1(0);
        for(auto pos : ret)
            if(N * 2 + 1 <= pos && pos <= N * 3)++cnt1;
            else if(1 <= pos && pos <= N)sorted += false;
        while(cnt1--)sorted += true;
        return;
    }
    basic_string < Edge* > sons;
    for(auto i = p->head; i; i = i->nxt)sons += i;
    sort(sons.begin(), sons.end(), [](Edge* a, Edge* b)->bool{return a->val < b->val;});
    for(auto son : sons)dfs(son->to);
}

int main(){
    // freopen("in.txt", "r", stdin);
    root = new Node(); root->idx = -1; root->len = 0;
    N = read();
    cin >> S >> T;
    base = '#' + S + S + T + T;
    for(int i = N * 4; i >= 1; --i)Insert(d(base.at(i)), i);
    Link(), dfs();
    ll ans(0), sumS(0);
    for(auto v : sorted)if(v)ans += sumS; else ++sumS;
    printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int idx(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')idx = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= idx;
    return ret;
}

UPD

update-2023__ 初稿

标签：Node,SAM,idx,int,link,Parent,浅析
From： https://www.cnblogs.com/tsawke/p/17180259.html