KMP / exKMP / AC自动机教程

定义1

$T$文本串,$P$模式串

$nxt[i]$:失配函数,表示$P[0,i)$的最大自匹配的真前缀和真后缀长度,$nxt[0]=-1$

性质:$nxt[i+1] \le nxt[i]+1$

上面的性质可用于递推构造$nxt$

(好像又没啥用)

构造过程

假设存在$i,j$指针,$i$为当前要处理的指针,而$j$对应于上一次$i-1$时匹配的失配指针

就是说有$nxt[i-1]=j$

说明最大的自匹配为$P[0,j]=P[t,i-1]$,$t$多少不必在意,只需知道两子串长度相等即可

对于$i$,假如$P[j+1]=P[i]$,前缀后缀就是前面的情况加上对应的$P[i]$,$nxt[i]=j+1$

否则就一直找失配函数的转移(因为我们是最大自匹配,所以失配的话$[nxt[j]+1,j-1]$都是已知的无用信息),$j=nxt[j]$的前移也意味着后缀$P[t,i]$的前缀缩短,直到找到$P[j+1]=P[i]$或者完全失配

由于每次$i$的迭代下$j$最多增长1(由性质1,这是最好的情况),而且也有失配带来的大量前移,因此这一部分显然是$O(n)$就能完成(另一种看法就是$P[t,i]$和$P[0,j]$的只缩不怎么涨,很形象看出复杂度)

构造过程在此结束(说不清道理,反正挺好求的)

匹配过程

其思路是$T$匹配的后缀可能性由$P$来提供

以$T$的后缀和$P$的前缀作为比较,此时$nxt$用于对付$T$的后缀失配的情况

同样的类似构造过程,假设存在$i,j$指针,$i$为当前要处理$T$的指针,而$j$对应于上一次$i-1$时匹配的$P$的失配指针

已知当前最大匹配$P[0,j]=T[t,i-1]$,同理$t$不要在意

我们希望这个过程$i$绝不回退,以$T[t,i]$来衡量$P$的后缀

确定这样的目标后,其实匹配过程和构造过程就几乎一致了

(有一点不同的是如果匹配过程$j$到达了$P$的长度就必须要回退,因为$P[j+1]$是非法的)

复杂度是$O(n+m)$

完成版

#include<bits/stdc++.h>
using namespace std;
string T,P;
vector<int> mat;
vector<int> nxt;
void build() {
    int j = -1, len = P.length();
    nxt = vector<int>(len);
    nxt[0] = -1;
    for(int i = 1; i < len; i++) {
        for(; j > -1 && P[i] != P[j+1]; j = nxt[j]);
        if(P[i] == P[j+1]) j++;
        nxt[i] = j;
    }
}
void match() {
    int j = -1, len = T.length();
    mat = vector<int>(len);
    for(int i = 0; i < len; i++) {
        for(; j < 0 ? false : j+1==len||T[i]!=P[j+1]; j = nxt[j]);
        if(T[i] == P[j+1]) j++;
        mat[i] = j;
    }
}
int main() {
    T = "aabababba";
    P = "aab";
    build();
    match();
    cout << T << endl
         << P << endl;
    for(auto i:mat) cout << i << " "; 
}

感觉EXKMP用处并不大,教程不写了


至于AC自动机,其实就是定义$fail[u]$为$root \to u$ 的最长相同后缀的转移节点

其余还有构造时的路径压缩,以及查询时可能用到的拓扑排序优化

然后没了

#include<bits/stdc++.h>
#define debug(xx) cout << "[line@" << __LINE__ << "] " << xx << endl
#define fast_io() do{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}while(0)
#define var auto
#define dect decltype
using namespace std;
using ll = int_fast64_t;
namespace util {
    template<typename T>
    inline void alloc(vector<T> &v) {
        v.emplace_back();
    }
    template<typename T>
    inline void empb(vector<T> &v,const T &arg) {
        v.emplace_back(arg);
    }
    template<typename T>
    inline void pb(vector<T> &v,const T &arg) {
        v.push_back(arg);
    }
}

using namespace util;
struct Trie {
    vector<array<int,26>> trie;
    vector<bool> flag;
    vector<int> ed;
    int root;
    Trie() {
        root = 0;
        empb(trie,{});
        empb(flag,false);
        empb(ed,0);
    }
    inline int state() {
        empb(trie,{});
        empb(flag,false);
        empb(ed,0);
        auto n = trie.size();  
        return n-1;
    }
    void add(const string &str) {
        auto cur = root;
        for(auto ch : str) {
            auto c = ch-'a';
            if(!trie[cur][c]) {
                auto t = state();
                trie[cur][c] = t;
//                trie[cur][c] = state(); // C++11会存在问题,C++17允许... 
//                debug(trie[cur][c] << " " << t << " " << cur);
            }
            cur = trie[cur][c];
        }
        flag[cur] = true;
        ed[cur]++;
    }

    array<int,26>& operator[](size_t pos) {
        return trie[pos];
    }
};
struct ac_automaton {
    Trie trie;
    vector<int> fail;
    int root;
    ac_automaton(vector<string> &strs) {
        root = 0;
        for(auto &str : strs) trie.add(str);
        fail.resize(trie.trie.size());
        queue<int> que;
        fail[root] = root;
        for(auto i = 0, j = 0; i < 26; i++) {
            if(j = trie[root][i]) {
                fail[j] = root;
                que.push(j);
            }
        }
        while(!que.empty()) {
            auto u = que.front(); que.pop();
            for(auto i = 0; i < 26; i++) {
                auto v = trie[u][i];
                auto f = fail[u];
                if(v) {
                    fail[v] = trie[f][i];
                    que.push(v);
                } else {
                    trie[u][i] = trie[f][i];
                }
            }
        }
    }
    ll query(const string &str) {
        auto cur = root;
        auto res = 0ll;
        for(auto ch : str) {
            auto c = ch-'a';
            cur = trie[cur][c];
            for(auto u = cur; u && ~trie.ed[u]; u = fail[u]) {
                res += trie.ed[u];
                trie.ed[u] = -1;
            }
        }
        return res;
    }
};
int main() {
    fast_io();
    int T; cin >> T;
    while(T--) {
        int n; cin >> n;
        vector<string> vec(n);
        for(auto &i : vec) cin >> i;
        ac_automaton ac(vec);
        string s;
        cin >> s;
        cout << ac.query(s) << endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注