HDU 2896(ウイルス侵襲)

ウイルスの侵襲
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
1行目は、ウイルス特徴コードの個数を表す整数N(1<=N<=500)である.
次のN行は、各行がウイルス特徴コードを表し、特徴コード文字列の長さは20〜200の間である.
各ウイルスには1～Nの番号が付けられています.
異なる番号のウイルスフィーチャーコードは同じではありません.
その後の行には、サイト数を表す整数M(1<=M<=1000)がある.
次にM行、各行は1つのウェブサイトのソースコードを表し、ソースコード文字列の長さは7000~10000の間である.
各サイトには1～Mの番号があります.
上記の文字列の文字はすべてASCIIコードの可視文字です(リターンは含まれません).
Output
以下のフォーマットで出力し、サイト番号で小さいから大きいまで出力し、ウイルス付きのサイト番号とウイルス番号を含み、各行に1つの毒入りサイト情報を出力します.
Webサイト番号:ウイルス番号ウイルス番号...
コロンの後にスペースがあり、ウイルス番号は小さいものから大きいものに並べられ、2つのウイルス番号の間には1つのスペースで区切られています.1つのサイトにウイルスが含まれている場合、ウイルス数は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;
}