MENU

回文自动机、AC自动机和后缀自动机介绍(1)

July 9, 2018 • Read: 2911 • 算法阅读设置

我们还从一个非常经典的题目出发,最长公共子串问题。给定两个字符串S和T,求S和T的最长公共子串的长度。比如abcdefg和abacabca的最长公共子串是abc

这是一道经典的动态规划问题,大致思路就是用fi表示同时以S[i]和T[j]结尾的最长公共子串的长度。下面看伪代码:

Ans = 0
For i = 1...S.len
    For j = 1...T.len
        If S[i] == T[i]
            F[i][j] = F[i - 1][j - 1] + 1
        If F[i][j] > Ans
            Ans = F[i][j]
Print Ans

DP的时间复杂度是O(S.len * T.len),但其实这道题利用后缀自动机,时间复杂度只到O(S.len + T.len),下图就是字符串”aabbabd”的后缀自动机:

后缀自动机就是能接受并且只接受S的后缀字符串。也就是说,你可以发现对于S的后缀,我们都可以从S出发沿着字符标示的路径(蓝色实线)转移,最终到达终结状态,也就是红色的节点

例如"bd"对应的路径是S59,"abd"对应的路径是S189,"abbabd"对应的路径是S184679。而对于不是S后缀的字符串,你会发现从S出发,最后会到达非终结状态或者“无路可走”。特别的,对于S的子串,最终会到达一个合法状态。例如"abba"路径是S1846,"bbab"路径是S5467。而对于其他不是S子串的字符串,最终会“无路可走”。 例如"aba"对应S18X,"aaba"对应S123X。(X表示没有转移匹配该字符)

首先我们先介绍一个概念:子串的结束位置集合endpos。对于S的一个子串t,endpos(t) = t在S中所有出现的结束位置集合。还是以S="aabbabd"为例,endpos("ab") = {3, 6},因为"ab"一共出现了2次,结束位置分别是3和6。同理endpos("a") = {1, 2, 5}, endpos("abba") = {5}

我们把S的所有子串的endpos都求出来。如果两个子串的endpos相等,就把这两个子串归为一类。最终这些endpos的等价类就构成的SAM的状态集合。例如对于S="aabbabd":

其中maxlen是一个状态包含的子串中,最长子串的长度。有了后缀自动机和每个状态的maxlen,我们就能求解S和T的最长公共子串了。具体做法是先求出S的后缀自动机,然后用T的每一个字符在S的后缀自动机上跑一遍。这里跑一遍的意思就是从初始状态开始,根据每一个字符T[i]在自动机的不同状态之间转移

举个例子,假设S=aabbabd,S的后缀自动机就是一开始的那张图

T=abbbaabbab。我们要找S和T的最长公共子串,就从状态S开始匹配,用u表示当前的状态,l表示当前匹配的长度。基本思路就是如果当前状态u没有标识T[i]的蓝色实线转移,我们就沿着绿色虚线向上找,不断令u等于u的绿色虚线指向的状态,同时令l = u.maxlen,直到u存在标识T[i]的转移或者u走到头了

如果最后u走到头了,我们就令u=S,l=0,从T[i+1]开始重新匹配。否则,我们就沿着蓝色实线转移,令u等于u的蓝色实线指向的状态,同时令l=l+1。然后再从T[i+1]继续匹配

具体来说,字符串T的完整匹配过程如下:
一开始u=S,l=0,我们要匹配T[1]=a,刚好u有标识a的边,所以我们直接移动到u=1, l=1

现在u=1, l=1,我们要匹配T[2]=b,刚好u有标识b的边,所以我们直接移动到u=8, l=2

现在u=8, l=2, 我们要匹配T[3]=b,刚好u有标识b的边,所以我们直接移动到u=4, l=3

现在u=4, l=3, 我们要匹配T[4]=b,u没有标识b的边,所以沿绿色退到u=5, l=maxlen[5]=1

现在u=5, l=1, 我们要匹配T[4]=b,u有标识a的边,所以我们移动到u=4, l=2

现在u=4, l=2, 我们要匹配T[5]=a,u有标识a的边,所以我们移动到u=6, l=3

现在u=6, l=3, 我们要匹配T[6]=a,u没有标识a的边,所以沿绿色退到u=1, l=maxlen[1]=1

现在u=1, l=1, 我们要匹配T[6]=a,u有标识a的边,所以我们移动到u=2, l=2

现在u=2, l=2, 我们要匹配T[7]=b,u有标识b的边,所以我们移动到u=3, l=3

现在u=3, l=3, 我们要匹配T[8]=b,u有标识b的边,所以我们移动到u=4, l=4

现在u=4, l=4, 我们要匹配T[9]=a,u有标识a的边,所以我们移动到u=6, l=5

现在u=6, l=5, 我们要匹配T[10]=b,u有标识b的边,所以我们移动到u=7, l=6

这样T就匹配完了,在匹配过程中,l的最大值就是最长公共子串的长度,也就是6。实际上匹配T[10]的时候l等于6,也意味着最长公共子串是T[5]~T[10]即:aabbab;同时u=7也意味着最长公共子串是状态7中长度为6的子串,从之前的表格中我们知道也是aabbab

对于字符串S,构建S的后缀自动机的复杂度是O(S.len)的;之后对T的每个字母跑一遍匹配,复杂度是O(T.len)。所以总的复杂度是O(S.len+T.len)。最后我们给出用后缀自动机求最长公共子串的代码:

#include<iostream>
#include<string>
using namespace std;
const int MAXL = 1000000;
string s, t;
int n = 0, len, st;
int maxlen[2 * MAXL + 10], minlen[2 * MAXL + 10], trans[2 * MAXL + 10][26], slink[2 * MAXL + 10];
int new_state(int _maxlen, int _minlen, int* _trans, int _slink) {
    maxlen[n] = _maxlen;
    minlen[n] = _minlen;
    for(int i = 0; i < 26; i++) {
        if(_trans == NULL) 
            trans[n][i] = -1;
        else 
            trans[n][i] = _trans[i];
    }
    slink[n] = _slink;
    return n++;
}
int add_char(char ch, int u) {
    int c = ch - 'a';
    int z = new_state(maxlen[u] + 1, -1, NULL, -1);
    int v = u;
    while(v != -1 && trans[v][c] == -1) {
        trans[v][c] = z;
        v = slink[v];
//        cout << v << endl;
    }
//    cout << z << endl;
    if(v == -1) {
        minlen[z] = 1;
        slink[z] = 0;
        return z;
    }
    int x = trans[v][c];
    if(maxlen[v] + 1 == maxlen[x]) {
        minlen[z] = maxlen[x] + 1;
        slink[z] = x;
        return z;
    }
    int y = new_state(maxlen[v] + 1, -1, trans[x], slink[x]);
    slink[y] = slink[x];
    minlen[x] = maxlen[y] + 1;
    slink[x] = y;
    minlen[z] = maxlen[y] + 1;
    slink[z] = y;
    int w = v;
    while(w != -1 && trans[w][c] == x) {
        trans[w][c] = y;
        w = slink[w];
    }
    minlen[y] = maxlen[slink[y]] + 1;
    return z;
}
int main()
{
    cin >> s >> t;
    len = s.size();
    st = new_state(0, 0, NULL, -1);
//    cout << trans[st][0] << endl;
    int u = st;
    for(int i = 0; i < len; i++) {
        int temp = add_char(s[i], u);
        u = temp;    
    }    
    u = st;
    int ans = 0, cur = 0;
    for(int i = 0; i < t.size(); i++) {
        int c = t[i] - 'a';
        while(u != -1 && trans[u][c] == -1) {
            u = slink[u];
            cur = maxlen[u];    
        }
        if(u == -1) {
            u = 0;
            cur = 0;
            continue;
        } 
        u = trans[u][c];
        cur++;
        if(cur > ans) ans = cur;
    }
    cout << ans << endl;
    return 0;
}
Last Modified: May 12, 2021
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment