本文主要是介绍ac自动机，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

模板

void insert() //建trie树
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int t = str[i] - 'a';
        if (!tr[p][t]) tr[p][t] = ++ idx;
        p = tr[p][t];
    }
    cnt[p] ++ ;
}

void build()
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i ++ )
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];//加入队列
    while(hh<=tt){
	int t=q[hh++];
	for(int i=0;i<26;i++){
		int c=tr[t][i];//看看她的儿子 
		if(!c) continue ;//可能没有 
		int j=next[t];//t这个结点可以向上匹配去到哪个位置 
		while(j&&!tr[j][i]) j=next[j];//如果j对应的第i个字符不存在说明没有找到相同的后缀 所以要再次跳转 
		if(tr[j][i]) j=tr[j][i];//最后如果找到了儿子 那么就走过去	 
		next[c]=j;//让next c等于那个字符  c是idx 
		q[++t]=c//多加一个idx 
	}
}


t= str[i]-'a'; 
for(int i=0,j=0;str[i];i++){
	int t=str[i]-'a';
	while(j&&!tr[j][t]) j=ne[j];//不存在这个结点就挑走 
	if(tr[j][t]) j=tr[j][t];//存在就走过去 找到匹配到最靠下的结点
	 
	
}

优化防止卡到

void build()
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i ++ )
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];//加入队列
    while(hh<=tt){
	int t=q[hh++];
	for(int i=0;i<26;i++){
		int p=tr[t][i];//看看她的儿子 
		if(!c) tr[t][i]=tr[ne[t]][i] ;//如果不存在 直接存下next应该走到的位置 下次不需要在词条 
		else{
                  ne[p]=tr[ne[t]][i];
                  q[++t]=p;
                  }
                 
             }

}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, S = 55, M = 1000010;

int n;
int tr[N * S][26], cnt[N * S], idx;
char str[M];
int q[N * S], ne[N * S];

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int t = str[i] - 'a';
        if (!tr[p][t]) tr[p][t] = ++ idx;//赋值一个结点
        p = tr[p][t];
    }
    cnt[p] ++ ;
}

void build()
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i ++ )
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];//队列 因为上面的操作 树已经建好了 这里看看根节点下面的对应字母 统计出第一层的各个结点

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = 0; i < 26; i ++ )
        {
            int p = tr[t][i];
            if (!p) tr[t][i] = tr[ne[t]][i];//如果不村子啊 直接跳到对应的最下方 下次直接用
            else
            {
                ne[p] = tr[ne[t]][i];
                q[ ++ tt] = p;
            }
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;

        scanf("%d", &n);
        for (int i = 0; i < n; i ++ )
        {
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str);

        int res = 0;
        for (int i = 0, j = 0; str[i]; i ++ )
        {
            int t = str[i] - 'a';
            j = tr[j][t];

            int p = j;
            while (p)
            {
                res += cnt[p];
                cnt[p] = 0;
                p = ne[p];
            }
        }

        printf("%d\n", res);
    }

    return 0;
}

这篇关于ac自动机的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！