[模板] AC自动机简单版

Zzzzzzzm · 2021-06-23 17:54:23 · 个人记录

#include<bits/stdc++.h>
using namespace std;

struct tree{
    int fail, num[27], end;
}AC[1000005];

int cnt, n;
string s; 

template<typename T>
inline void read(T&x){
    x = 0; char q; bool f = 1;
    while(!isdigit(q = getchar()))  if(q == '-')    f = 0;
    while(isdigit(q)){
        x = (x<<1) + (x<<3) + (q^48);
        q = getchar();
    }
    x = f?x:-x;
}

template<typename T>
inline void write(T x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)   write(x/10);
    putchar(x%10+'0');
}

inline void build(string s){
    int lenth = s.size();
    int now = 0;
    for(register int i = 0; i < lenth; ++i){
        if(AC[now].num[s[i]-'a'] == 0)
            AC[now].num[s[i]-'a'] = ++cnt;
        now = AC[now].num[s[i]-'a'];
    }
    AC[now].end++;
}

void Get_fail(){
    queue<int> q;
    for(register int i = 0; i < 26; ++i){
        if(AC[0].num[i]){
            AC[AC[0].num[i]].fail = 0;
            q.push(AC[0].num[i]);
        }
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(register int i = 0; i < 26; ++i){
            if(AC[u].num[i]){
                AC[AC[u].num[i]].fail = AC[AC[u].fail].num[i];
                q.push(AC[u].num[i]);
            }
            else    AC[u].num[i] = AC[AC[u].fail].num[i];
        }
    }
}

int AC_query(string s){
    int lenth = s.size();
    int now = 0, ans = 0;
    for(register int i = 0; i < lenth; ++i){
        now = AC[now].num[s[i]-'a'];
        for(register int j = now; j && AC[j].end != -1; j = AC[j].fail){
            ans += AC[j].end;
            AC[j].end = -1;
        }
    }
    return ans;
}

int main(){
    read(n);
    for(register int i = 1; i <= n; ++i){
        cin >> s;
        build(s);
    }
    AC[0].fail = 0;
    Get_fail();
    cin >> s;
    cout << AC_query(s);
    return 0;
}