題面：

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

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

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

2 3 1 0

題意：

? ?額，中文大家都懂。

解題：

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

代碼：

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