HDU 2896

AC自动机应用，隔了两三天再写稍显生疏，还是需要练习提高熟练度。

自动机状态数其实是个不太好估量的数字，本题查看discuss才发现，内存会被卡

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <deque>
using namespace std;

const int maxc= 101;
const int maxs= 58030;
const int maxv= 205;
const int maxw= 10005;
const int maxn= 500;

struct Trie
{
	int root, L;
	int next[maxs][maxc], end[maxs], fail[maxs];
	void Init()
	{
		L= 0;
		root= NewNode();
	}
	int NewNode()
	{
		for (int i= 0; i< maxc; ++i){
			next[L][i]= -1;
		}
		end[L++]= 0;
		return L-1;
	}
	void Insert(char *s, int id)
	{
		int lth= strlen(s), now= root;
		for (int i= 0; i< lth; ++i){
			int idx= s[i]-' ';
			if (-1== next[now][idx]){
				next[now][idx]= NewNode();
			}
			now= next[now][idx];
		}
		end[now]= id;
	}
	void Build()
	{
		queue<int> Q;
		fail[root]= root;
		for (int i= 0; i< maxc; ++i){
			if (-1== next[root][i]){
				next[root][i]= root;
			}
			else{
				fail[next[root][i]]= root;
				Q.push(next[root][i]);
			}
		}

		while (!Q.empty()){
			int now= Q.front();
			Q.pop();

			for (int i= 0; i< maxc; ++i){
				if (-1== next[now][i]){
					next[now][i]= next[fail[now]][i];
				}
				else{
					fail[next[now][i]]= next[fail[now]][i];
					Q.push(next[now][i]);
				}
			}
		}
	}
	int Query(char *s, int diag[])
	{
		int tot= 0, lth= strlen(s);
		int now= root;

		for (int i= 0; i< lth; ++i){
			int idx= s[i]-' ';
			now= next[now][idx];
			int tmp= now;

			while (root!= tmp){
				if (end[tmp]){
					int flag= 1;
					for (int i= 0; i< tot; ++i){
						if (diag[i]== end[tmp]){
							flag= 0;
							break;
						}
					}
					if (flag){
						diag[tot++]= end[tmp];
						if (tot>= 3){
							goto RET;
						}
					}
				}
				tmp= fail[tmp];
			}
		}

	RET: sort(diag, diag+tot);
		return tot;
	}
}ac;
char virus[maxv], web[maxw];
int diag[4];

int main(int argc, char const *argv[])
{
	int n, m;
	scanf("%d", &n);
	ac.Init();
	for (int i= 1; i<= n; ++i){
		scanf(" %s", virus);
		ac.Insert(virus, i);
	}
	ac.Build();

	scanf("%d", &m);
	int cnt= 0;
	for (int i= 1; i<= m; ++i){
		scanf(" %s", web);
		int tot= ac.Query(web, diag);
		if (tot> 0){
			++cnt;
			printf("web %d:", i);
			for (int j= 0; j< tot; ++j){
				printf(" %d", diag[j]);
			}
			putchar('
');
		}
	}

	printf("total: %d
", cnt);
	return 0;
}