AC自动机

2024-08-11

采用字典树和KMP算法的思想,实现字符串的多模式匹配问题

#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-7
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 10005;
struct node
{
    int son[26];
    int end;
    int fail;
} t[N];
int cnt = 1;
void Insert(char *s)
{
    int now = 0;
    for (int i = 0; s[i]; i++)
    {
        int ch = s[i] - 'a';
        if (t[now].son[ch] == 0)
            t[now].son[ch] = cnt++;
        now = t[now].son[ch];
    }
    t[now].end++;
}
void getFail()
{
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (t[0].son[i])
            q.push(t[0].son[i]);
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
        {
            if (t[now].son[i])
            {
                t[t[now].son[i]].fail = t[t[now].fail].son[i];
                q.push(t[now].son[i]);
            }
            else
                t[now].son[i] = t[t[now].fail].son[i];
        }
    }
}
int query(char *s)
{
    int ans = 0, now = 0;
    for (int i = 0; s[i]; i++)
    {
        int ch = s[i] - 'a';
        now = t[now].son[ch];
        int tmp = now;
        while (tmp && t[tmp].end != -1)
        {
            ans += t[tmp].end;
            t[tmp].end = -1;
            tmp = t[tmp].fail;
        }
    }
    return ans;
}
char str[N];
int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%s", str);
        Insert(str);
    }
    getFail();
    scanf("%s", str);
    printf("%d\n", query(str));
    return 0;
}