統(tǒng)計難題 （字典樹，val值統(tǒng)計經(jīng)過該點的字母數(shù)量）

題面：

統(tǒng)計難題 Time Limit: 4000/2000 MS (Java/Others)????Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 25921????Accepted Submission(s): 10560


Problem Description Ignatius最近遇到一個難題,老師交給他很多單詞(只有小寫字母組成,不會有重復的單詞出現(xiàn)),現(xiàn)在老師要他統(tǒng)計出以某個字符串為前綴的單詞數(shù)量(單詞本身也是自己的前綴).
?
Input 輸入數(shù)據(jù)的第一部分是一張單詞表,每行一個單詞,單詞的長度不超過10,它們代表的是老師交給Ignatius統(tǒng)計的單詞,一個空行代表單詞表的結(jié)束.第二部分是一連串的提問,每行一個提問,每個提問都是一個字符串.

注意:本題只有一組測試數(shù)據(jù),處理到文件結(jié)束.
?
Output 對于每個提問,給出以該字符串為前綴的單詞的數(shù)量.
?
Sample Input

banana band bee absolute acm ba b band abc ?
Sample Output

2 3 1 0

題意：

? ?額，中文大家都懂。

解題：

? ? 字典樹裸題，val值統(tǒng)計經(jīng)過該點的字母數(shù)量。

代碼：

#include#include#include#includeusing?namespace?std;
struct?Trie
{
	//用來儲存該節(jié)點的26個字母下標，ch的第一維要注意，要開大，不然會T?
	int?ch[1000010][26];
	//val數(shù)組一般用來存儲權(quán)值，視題目靈活運用，sz是當前節(jié)點數(shù)量
	int?val[1000010],sz;
	//初始化
	void?init()
	{
		sz=1;
		memset(ch[0],0,sizeof(ch[0]));
	}
	//插入一條單詞
	void?insert(string?s)
	{
		//u是節(jié)點編號，并不是層數(shù)
		int?u=0,len=s.length();
		for(int?i=0;i<len;i++)
		{
			//取下標
			int?c=(s[i]-'a');
			//如果該節(jié)點不存在，創(chuàng)建該節(jié)點
			if(!ch[u][c])
			{
				//真的是相當?shù)氖?				memset(ch[sz],0,sizeof(ch[sz]));
				//因為剛創(chuàng)建所以為1
				val[sz]=1;
				//給該節(jié)點分配編號
				ch[u][c]=sz++;
				//下移
				u=ch[u][c];
			}
			//已經(jīng)存在了
			else
			{
			??//下移，并計數(shù)值加一
			??u=ch[u][c];
		??????val[u]++;
			}
		}
	}
	//查詢前綴
	int?query(string?s)
	{
		int?len=s.length(),u=0,c;
		//不斷下移，直至移到給定的前綴的最后一個單詞
		bool?sign=true;
		for(int?i=0;i<len;i++)
		{
		???c=s[i]-'a';
		???if(ch[u][c])
?????????????u=ch[u][c];
???????????else
???????????{
??????????????sign=false;
??????????????break;
???????????}
		}
		if(sign)
??????????return?val[u];
????????else
??????????return?0;
	}
};
Trie?T;
int?main()
{
????????string?s;
????????T.init();
????????while(getline(cin,s))
????????{
???????????if(s=="")break;
???????????T.insert(s);
????????}
????????while(getline(cin,s))
????????{
???????????cout<<T.query(s)<<endl;
????????}
	????return?0;
}