Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

KMP & Trie & AC自动机 模板

发表于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟
标签：                

用于字符串问题。

KMP

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
nxt[1] = 0;
for (int i = 1, j = 0; i < s.size(); i++)
{
    while (j && s[i] != s[j])
        j = nxt[j];
    if (s[i] == s[j])
        j++;
    nxt[i + 1] = j;//此时i与j - 1是匹配的，当i + 1不能匹配时可以尝试j
}
for (int i = 0, j = 0; i < t.size(); i++)
{
    while (j && t[i] != s[j])
        j = nxt[j];
    if (t[i] == s[j])
        j++;
    if (j == s.size())
    {
        cout << i - s.size() + 2 << endl;
        j = nxt[j];
    }
}

例：$abcabdababcabc$ 中匹配 $abcabc$

性质：一段前缀区间里的前缀等于后缀。

大多数 $KMP$ 模板的字符需要从 $1$ 开始，这里提供一种直接从 $0$ 开始的模板。

但是注意，这里的 $nxt$ 数组是从 $1$ 开始的。

Trie

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct trie
{
    int nxt[N][26], cnt;
    bool exist[N];
    void insert(char *s, int l)
    {
        int p = 0;
        for (int i = 0; i < l; i++)
        {
            int c = s[i] - 'a';
            if (!nxt[p][c])
                nxt[p][c] = ++cnt;
            p = nxt[p][c];
        }
        exist[p] = 1;
    }
    bool find(char *s, int l)
    {
        int p = 0;
        for (int i = 0; i < l; i++)
        {
            int c = s[i] - 'a';
            if (!nxt[p][c])
                return 0;
            p = nxt[p][c];
        }
        return exist[p];
    }
};

AC自动机

$AC自动机 = KMP + Trie$

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
void build()
{
    queue<int> q;
    for (int i = 0; i < 26; i++)
        tr[0][i] && (q.push(tr[0][i]), 0);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
        {
            int &p = tr[t][i];
            if (!p)
                p = tr[nxt[t]][i];
            else
            {
                nxt[p] = tr[nxt[t]][i];
                q.push(p);
            }
        }
    }
}
void insert(int k, int len, char *str)
{
    int p = 0;
    for (int i = 1; i <= len; i++)
    {
        int &t = tr[p][str[i] - 'a'];
        !t && (t = ++idx);
        p = t;
        cnt[p] = true;
    }
    id[k] = p;
}
void dfs(int x)
{
    for (int i : g[x])
    {
        dfs(i);
        f[x] += f[i];
    }
}
int main()
{
    read(n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s + 1);
        insert(i, strlen(s + 1), s);
    }
    build();
    scanf("%s", str + 1);
    int m = strlen(str + 1);
    for (int i = 1, p = 0; i <= m; i++)
    {
        int t = str[i] - 'a';
        p = tr[p][t];
        f[p] += cnt[p];
    }
    for (int i = 1; i <= idx; i++)
        g[nxt[i]].push_back(i);
    dfs(0);
    for (int i = 1; i <= n; i++)
        write(f[id[i]]), puts("");
    return 0;
}

对于当前节点 $t$ ，对于每一个下一个字符 $tr[t][i]$ ，如果不存在，那么将它指向失配后的节点的下一个 $i$ ；如果存在，那么 $tr[t][i]$ 的子节点如果失配了，可以考虑再尝试不选择 $tr[t][i]$ ，而是选择其失配后的节点的下一个 $i$ ，即$nxt[tr[t][i]] = tr[nxt[t]][i]$ 。

可以理解，对于一个节点不断找到 $nxt$ ，它们都是在文本串的子串，匹配时每到一个节点，都需要将其所有的 $nxt$ 找完才能让所有模式串得到答案。可以发现除了根节点，每个节点都有一个 $nxt$ ，因此构成了一棵树，处理时可以用树形DP。

相关文章