2017-10-22

后缀自动机（待完善）

后缀自动机的能解决的问题及一些个人的理解
任何一个节点所代表的最短的串一定比link前面的节点代表的最长串大1，所代表的最长的串比后面的最短的串短1.

参考文献

由于本文基本参照的是他人的思路，故先放出他人的文章，写的都很好。
SUFFIX AUTOMATON by- saisumit
A short guide to suffix automata
后缀自动机与线性构造后缀树
这篇文章讲了建立后缀自动机的过程其实就是建立了一棵原串逆序后的后缀树(reversed raw string)。

建后缀自动机过程及代码

建立后缀自动机是不断的加入原串的前缀的。
两条性质：

从任意节点开始到terminal node(带*的节点)的所有路径，是原串的后缀。这些后缀集合要么是集合的从属关系，要么是互不相交的关系。
从初始点开始到任意的节点，可以得到原串的所有的子串。

我们可以通过endpos集合的分类，以及任何一个节点所代表的最短的串一定比link前面的节点代表的最长串大1，所代表的最长的串比后面的最短的串短1这个性质，构造出一个link[]维护的东西。形成了一棵有集合包含关系的后缀树。

下面通过s = “dababd”的例子来进一步说明。维护后缀自动机的过程就是相当于维护后缀树。维护后缀自动机子串最长公共后缀的过程就是不断维护后缀树最长公共前缀的过程

#include <bits/stdc++.h>
using namespace std;
struct state {
    int len, link;
    map<char,int>next;
};
const int MAXLEN = 100000;
state st[MAXLEN*2];
int sz, last;
void sa_init() {
    sz = last = 0;
    st[0].len = 0;
    st[0].link = -1;
    st[0].next.clear();
    ++sz;}
void sa_extend (char c) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p;
    for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link)
        st[p].next[c] = cur;
    if (p == -1)
        st[cur].link = 0;
    else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len)
            st[cur].link = q;
        else {
            int clone = sz++;
            //printf("%dclone\n", p);
            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next;
            st[clone].link = st[q].link;
            for (; p!=-1 && st[p].next[c]==q; p=st[p].link)
                st[p].next[c] = clone;
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}
int main()
{
    sa_init();
    sa_extend('a');
    sa_extend('b');
    sa_extend('b');
    sa_extend('a');
    sa_extend('b');
    return 0;
}

所能解决的问题

代码待更新

文本串中不同种类的子串的个数

就是性质里面的第二条，从起点dfs进行统计即可。（路径两两是不相交的）

所有子串的长度和

字典序第k大的子串

位移多少次之后得到的串字典序最小

所给的串在原串中第一次出现的位置

计算子串出现的次数

kmp也可以，时间复杂度都是O(n)

两个串中的最长公共子串

dp做是O\((n^2)\)的复杂度，可见后缀自动机的优势

多个串的最长公共子串

见clj的课件

最短的没有在原串中出现的子串

未解决的问题

本文标题:后缀自动机（待完善）

文章作者:Babydragon

发布时间:2017-10-22, 01:08:23

最后更新:2018-03-23, 13:35:51

原始链接:http://baolintian.github.io/2017/10/22/后缀自动机/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。