HDU2896(病毒侵袭)

病毒侵袭

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2557    Accepted Submission(s): 667


Problem Description
当太阳的光辉逐渐被月亮遮蔽，世界失去了光明，大地迎来最黑暗的时刻。。。。在这样的时刻，人们却异常兴奋——我们能在有生之年看到500年一遇的世界奇观，那是多么幸福的事儿啊~~
但网路上总有那么些网站，开始借着民众的好奇心，打着介绍日食的旗号，大肆传播病毒。小t不幸成为受害者之一。小t如此生气，他决定要把世界上所有带病毒的网站都找出来。当然，谁都知道这是不可能的。小t却执意要完成这不能的任务，他说：“子子孙孙无穷匮也！”（愚公后继有人了）。
万事开头难，小t收集了好多病毒的特征码，又收集了一批诡异网站的源码，他想知道这些网站中哪些是有病毒的，又是带了怎样的病毒呢？顺便还想知道他到底收集了多少带病毒的网站。这时候他却不知道何从下手了。所以想请大家帮帮忙。小t又是个急性子哦，所以解决问题越快越好哦~~



Input
第一行，一个整数N（1<=N<=500），表示病毒特征码的个数。
接下来N行，每行表示一个病毒特征码，特征码字符串长度在20—200之间。
每个病毒都有一个编号，依此为1—N。
不同编号的病毒特征码不会相同。
在这之后一行，有一个整数M（1<=M<=1000），表示网站数。
接下来M行，每行表示一个网站源码，源码字符串长度在7000—10000之间。
每个网站都有一个编号，依此为1—M。
以上字符串中字符都是ASCII码可见字符（不包括回车）。



Output
依次按如下格式输出按网站编号从小到大输出，带病毒的网站编号和包含病毒编号，每行一个含毒网站信息。
web 网站编号: 病毒编号 病毒编号 …
冒号后有一个空格，病毒编号按从小到大排列，两个病毒编号之间用一个空格隔开，如果一个网站包含病毒，病毒数不会超过3个。
最后一行输出统计信息，如下格式
total: 带病毒网站数
冒号后有一个空格。



Sample Input
3
aaa
bbb
ccc
2
aaabbbccc
bbaacc


Sample Output
web 1: 1 2 3
total: 1

用kmp和trie树都超时
kmp代码:

#include <iostream>
using namespace std;

int next[501][205];
char web[10001][10005];
char code[501][205];

void getNext(char c[], int cns)
{
	int len = strlen(c);
	int i = 0, j = -1;
	next[cns][0] = -1;
	while(i < len)
	{
		if(j == -1 || c[i] == c[j])
		{
			i++; j++;
			if(c[i] == c[j])
				next[cns][i] = next[cns][j];
			else
				next[cns][i] = j;
		}else
			j = next[cns][j];
	}
}

bool kmp(char w[], char c[], int cns)
{
	int i = 0, j = 0;
	int wlen = strlen(w), clen = strlen(c);
	while(i < wlen && j < clen)
	{
		if(j == -1 || w[i] == c[j])
		{
			i++; j++;
		}else
			j = next[cns][j];
	}
	if(j == clen)
		return true;
	return false;
}
int main()
{
	int n, m, i, j, total;
	bool flag;
	while(cin>>n)
	{
		for(i = 0; i < n; i++)
		{
			cin>>code[i];
			getNext(code[i], i);
		}
		cin>>m;
		total = 0;
		for(i = 0; i < m; i++)
		{
			cin>>web[i];
			flag = true;
			for(j = 0; j < n; j++)
			{
				if(kmp(web[i], code[j], j))
					if(flag)
					{
						cout<<"web "<<i + 1<<":"<<" "<<j + 1;
						total++;
						flag = false;
					}
					else
						cout<<" "<<j + 1;
			}
			if(!flag)
				cout<<endl;
		}
		cout<<"total: "<<total<<endl;
	}
	return 0;
}

trie树代码:

#include <iostream>
using namespace std;

const int branch = 100;

char code[205];
char web[10005];
bool flag;
int total;

typedef struct trie_node{
	bool isword;
	bool isMatch;
	int rank;
	struct trie_node *next[branch];
	trie_node():isword(false), rank(0), isMatch(false)
	{
		memset(next, NULL, sizeof(next));
	}
}*pTrie_Node;

class Trie{
private:
	pTrie_Node root;
public:
	Trie()
	{
		root = new trie_node();
	}
	pTrie_Node getRoot()
	{
		return root;
	}
	void insert(const char *word, int r);
	void destory(pTrie_Node cur);
	void search(const char *word, int r);
	void clear(pTrie_Node cur);
};

void Trie::insert(const char *word, int r)
{
	pTrie_Node loc = root;
	while(*word && loc)
	{
		if(loc->next[*word - 31] == NULL)
			loc->next[*word - 31] = new trie_node();
		loc = loc->next[*word - 31];
		word++;
	}
	loc->isword = true;
	loc->rank = r;
}

void Trie::destory(pTrie_Node cur)
{
	for(int i = 0; i < branch; i++)
		if(cur->next[i] != NULL)
			destory(cur->next[i]);
	delete cur;
}

void Trie::search(const char *word, int r)
{
	pTrie_Node loc = root;
	while(*word && loc)
	{
		loc = loc->next[*word - 31];
		if(loc && loc->isword && !loc->isMatch)
		{
			if(flag)
			{
				cout<<"web "<<r<<":"<<" "<<loc->rank;
				total++;
				flag = false;
			}else
				cout<<" "<<loc->rank;
			loc->isMatch = true;
		}
		word++;
	}
}

void Trie::clear(pTrie_Node cur)
{
	for(int i = 0; i < branch; i++)
		if(cur->next[i] != NULL)
			clear(cur->next[i]);
	if(cur->isword)
		cur->isMatch = false;
}
int main()
{
	int n, m, i, j, len;
	while(cin>>n)
	{
		Trie t;
		for(i = 1; i <= n; i++)
		{
			cin>>code;
			t.insert(code, i);
		}
		cin>>m;
		total = 0;
		for(i = 1; i <= m; i++)
		{
			flag = true;
			cin>>web;
			len = strlen(web);
			for(j = 0; j < len; j++)
			{
				t.search(&web[j], i);
			}
			t.clear(t.getRoot());
			if(!flag)
				cout<<endl;
		}
		cout<<"total: "<<total<<endl;
		t.destory(t.getRoot());
	}
	return 0;
}