【luogu P3808 AC自动机（简单版）】模板

题目链接：https://www.luogu.org/problemnew/show/P3808

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 1000010;

int n, trie[maxn][27], next[maxn], tot, vis[maxn];

char s[maxn];

queue<int> q;

void _insert(char s[])

{

    int now = 0;

    int len = strlen(s);

    for(int i = 0; i < len; i++)

    {

        int x = s[i]-'a';

        if(!trie[now][x])

        trie[now][x] = ++tot;

        now = trie[now][x];

    }

    vis[now]++;

}

void get_next()

{

    for(int i = 0; i < 26; i++)

    {

        if(trie[0][i])

        {

            next[trie[0][i]] = 0;

            q.push(trie[0][i]);

        }

    }

    while(!q.empty())

    {

        int cnt = q.front(); q.pop();

        for(int i = 0; i < 26; i++)

        {

            if(trie[cnt][i])

            {

                next[trie[cnt][i]] = trie[next[cnt]][i];

                q.push(trie[cnt][i]);

            }

            else

            trie[cnt][i] = trie[next[cnt]][i];

        }

    }

}

int find(char s[])

{

    int now = 0, ans = 0;

    int len = strlen(s);

    for(int i = 0; i < len; i++)

    {

        int x = s[i]-'a';

        now = trie[now][x];

        for(int k = now; k&&~vis[k]; k = next[k])

        {

            ans += vis[k];

            vis[k] = -1;

        }

    }

    return ans;

}

int main()

{

    std::ios::sync_with_stdio(false);

    cin>>n;

    for(int i = 1; i <= n; i++)

    {

        cin>>s;

        _insert(s);

    }

    get_next();

    cin>>s;

    cout<<find(s);

    return 0;

}

巴特西

【luogu P3808 AC自动机（简单版）】模板

最新文章

热门文章

巴特西

【luogu P3808 AC自动机（简单版）】 模板

最新文章

热门文章

【luogu P3808 AC自动机（简单版）】模板