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

传送门：https://www.luogu.org/problem/P3808
题解：是一个AC自动机的裸题了，注释加在代码里面了
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 5, sigma_size = 26;

int ch[maxn][sigma_size];

int tot;       //结点总数

int ans = 0;

int f[maxn];  //失配函数

int last[maxn];//表示 i沿着失配指针往回走时，遇到的下一个单词结点(即是该单词的最后一个结点)的编号

int val[maxn]; //若值不为0表示该结点是单词的最后一个结点

char a[maxn];

char b[maxn];

void init()

{

    tot = 1;

    memset(val, 0, sizeof(val));

    memset(ch, 0, sizeof(ch));

    memset(f, 0, sizeof(f));

    memset(last, 0, sizeof(last));

}

void insert(char *str)//将所有模式串构建成一个字典树

{

    int p = 0;

    int len = strlen(str);

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

    {

        int c = str[i] - 'a';

        if(!ch[p][c])

        {

            ch[p][c] = tot++;

        }

        p = ch[p][c];

    }

    val[p] ++;//标记此结点为末尾 同时代表模式串中 相同的字符串有几个

}

void find(char *str)

{

    int n = strlen(str);

    int u = 0;

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

    {

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

        while(u && !ch[u][s])

            u = f[u];

        u = ch[u][s];

        if(val[u])

        {

            ans += val[u];

            val[u] = 0;

        }

        else if(val[last[u]])//判断是否为单词的末尾结点

        {

            ans += val[last[u]];

            val[last[u]] = 0;

        }

    }

}

void getfail()//通过BFS进行计算fail函数

{

    queue<int> q;

    f[0] = 0;

    for(int c = 0; c < sigma_size; c++)

    {

        int u = ch[0][c];

        if(u)//将所有根结点的孩子结点全部压入队列

        {

            f[u] = 0;//根结点的孩子结点失配只能跳到根结点

            q.push(u);

            last[u] = 0;

        }

    }

    while(!q.empty())

    {

        int r = q.front();

        q.pop();

        for(int c = 0; c < sigma_size; c++)

        {

            int u = ch[r][c];

            if(!u)

                continue;//{ch[r][c]=ch[f[r]][c];continue}(则可以把while语句删除)，路径压缩

            q.push(u);

            int v = f[r];

            while(v && !ch[v][c])//沿着失配边走  直到可以匹配  和KMP类似

                v = f[v];

            f[u] = ch[v][c];

            last[u] = val[f[u]] ? f[u] : last[f[u]];//last需要指向单词末尾  用val数组判断

        }

    }

}

int main(void)

{

    int n;

    scanf("%d", &n);

    init();

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

    {

        scanf("%s", a);

        insert(a);//根据情况而定 还可以改为insert(a,value) ;表示该单词的权重

    }

    getfail();

    scanf("%s", b);

    find(b);

    cout << ans << endl;

    return 0;

}
巴特西

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

最新文章

热门文章
