HDU 2896 病毒侵袭 AC自动机裸题

题目来源：HDU 2896 病毒侵袭

题意：求文本串中有多少个模式串 并且输出下标

思路：直接ac自动机 然后数组记录在输出

我日写了半天结果函数没调用 找了半天错误 你要长记性啊 这种错误犯了好几次了啊 笨蛋

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 10010;
char a[maxn];
bool vis[maxn];
int ans, m;

const int maxnode = 500*210;
const int size = 128;
int ch[maxnode][size];
int val[maxnode];
int f[maxnode];
int sz;
bool id[maxn];
void init()
{
	sz = 1;
	memset(ch[0], 0, sizeof(ch[0]));
}
void insert(char *s, int v)
{
	int u = 0, n = strlen(s);
	for(int i = 0; i < n; i++)
	{
		int c = s[i];
		if(!ch[u][c])
		{
			memset(ch[sz], 0, sizeof(ch[sz]));
			val[sz] = 0;
			ch[u][c] = sz++;
		}
		u = ch[u][c];
	}
	val[u] = v;
}
void getFail()
{
	queue <int> q;
	f[0] = 0;
	for(int c = 0; c < size; c++)
	{
		int u = ch[0][c];
		if(u)
		{
			f[u] = 0;
			q.push(u);
		}
	}
	while(!q.empty())
	{
		int r = q.front(); q.pop();
		
		for(int c = 0; c < size; c++)
		{
			int u = ch[r][c];
			if(!u)
			{
				ch[r][c] = ch[f[r]][c];
				continue;
			}
			q.push(u);
			f[u] = ch[f[r]][c];
		}
	}
}

void find(char *s, int num)
{
	memset(id, 0, sizeof(id));
	int n = strlen(s);
	int j = 0;
	int flag = 0;
	for(int i = 0; i < n; i++)
	{
		j = ch[j][s[i]];
		int temp = j;
		while(temp)
		{
			if(val[temp] > 0)
			{
				id[val[temp]] = true;
				
				flag = 1;
			}
			temp = f[temp];
		}
	}
	if(!flag)
		return;
	ans++;
	printf("web %d:", num);
	for(int i = 1; i <= m; i++)
		if(id[i])
			printf(" %d", i);
	puts("");
	
}
int main()
{
	int n;
	while(scanf("%d", &n) != EOF)
	{
		m = n;
		init();
		for(int i = 1; i <= n; i++)
		{
			char s[555];
			scanf("%s", s);
			insert(s, i);
		}
		getFail();
		ans = 0;
		int t;
		scanf("%d", &t);
		for(int i = 1; i <= t; i++)
		{
			scanf("%s", a);
			find(a, i);
		}
		printf("total: %d\n", ans);
	}
	return 0;
}

HDU 2896 病毒侵袭 AC自动机裸题,布布扣,bubuko.com

HDU 2896 病毒侵袭 AC自动机裸题

原文：http://blog.csdn.net/u011686226/article/details/23762269