Java教程

做题记录 Luogu P3808

本文主要是介绍做题记录 Luogu P3808,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Luogu P3808 【模板】AC自动机(简单版)

模板,没太理解到呢。

Flag :明天再打一遍。

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int n;
namespace AC
{
	int tr[N][26], tot;
	int e[N], fail[N];
	void insert(char *s)
	{
		int u = 0;
		for(int i = 1; s[i]; i++)
		{
			if(!tr[u][s[i] - 'a'])
			{
				tr[u][s[i] - 'a'] = ++tot;
			}
			u = tr[u][s[i] - 'a'];
		}
		e[u]++;
		return;
	}
	queue<int> q;
	void build()
	{
		for(int i = 0; i < 26; i++)
		{
			if(tr[0][i])
			{
				q.push(tr[0][i]);
			}
		}
		while(!q.empty())
		{
			int u = q.front();
			q.pop();
			for(int i = 0; i < 26; i++)
			{
				if(tr[u][i])
				{
					fail[tr[u][i]] = tr[fail[u]][i];
					q.push(tr[u][i]);
				}
				else
				{
					tr[u][i] = tr[fail[u]][i];
				}
			}
		}
		return;
	}
	int query(char *s)
	{
		int u = 0, ret = 0;
		for(int i = 1; s[i]; i++)
		{
			u = tr[u][s[i] - 'a'];
			for(int j = u; j && e[j] != -1; j = fail[j])
			{
				ret += e[j];
				e[j] = -1;
			}
		}
		return ret;
	}
}
char s[N];
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%s", s + 1);
		AC::insert(s);
	}
	scanf("%s", s + 1);
	AC::build();
	printf("%d", AC::query(s));
	return 0;
}
这篇关于做题记录 Luogu P3808的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!