HDU 5384字典树运用

题面：

Danganronpa Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 512    Accepted Submission(s): 284


Problem Description Danganronpa is a video game franchise created and developed by Spike Chunsoft, the series' name is compounded from the Japanese words for "bullet" (dangan) and "refutation" (ronpa).

Now, Stilwell is playing this game. There are n verbal evidences, and Stilwell has m "bullets". Stilwell will use these bullets to shoot every verbal evidence.

Verbal evidences will be described as some strings Ai, and bullets are some strings Bj. The damage to verbal evidence Ai from the bullet Bj is f(Ai,Bj).
f(A,B)=∑i=1|A|−|B|+1[ A[i...i+|B|−1]=B ] In other words, f(A,B) is equal to the times that string B appears as a substring in string A.
For example: f(ababa,ab)=2, f(ccccc,cc)=4

Stilwell wants to calculate the total damage of each verbal evidence Ai after shooting all m bullets Bj, in other words is ∑mj=1f(Ai,Bj).  
Input The first line of the input contains a single number T, the number of test cases.
For each test case, the first line contains two integers n, m.
Next n lines, each line contains a string Ai, describing a verbal evidence.
Next m lines, each line contains a string Bj, describing a bullet.

T≤10
For each test case, n,m≤105, 1≤|Ai|,|Bj|≤104, ∑|Ai|≤105, ∑|Bj|≤105
For all test case, ∑|Ai|≤6∗105, ∑|Bj|≤6∗105, Ai and Bj consist of only lowercase English letters  
Output For each test case, output n lines, each line contains a integer describing the total damage of Ai from all m bullets, ∑mj=1f(Ai,Bj).  
Sample Input

1 5 6 orz sto kirigiri danganronpa ooooo o kyouko dangan ronpa ooooo ooooo  
Sample Output

1 1 0 3 7  
Author SXYZ  
Source 2015 Multi-University Training Contest 8

解题：

    比赛的时候，看到那么多人过了，也想着套套AC自动机，但不会就是不会呀。没有基础，赛后搜题解发现有人用字典树过了，就学习一下。虽然感觉复杂度上可能会超，但学习一下字典树也是不错的嘛！字典树的查询和构建是唯一的难点。因为刚接触还是不是很会，就参考了这篇博客的做法。

    其实就是先将所有的B构建成一颗字典树，然后枚举每个A，从A的不同起始位置开始去匹配B，查询函数可以这样理解。当用A的一部分移动到B的字典树的某一节点时，说明当前往上的节点都已经匹配成功了，那么也就是A中包含由B的根节点到当前节点形成的路径，那么加上该节点对应的数量即可，一旦匹配失败，那么再往下也不可能了，直接返回此时的数量就好了。

代码：

#include#include#includeusing namespace std;
struct Trie
{
	//存储的节点
	int ch[100010][26];
	//val存储的是节点权值，sz是节点数量
	int val[100010],sz;
	//初始化
	void init()
	{
		sz=1;
		memset(ch[0],0,sizeof(ch[0]));
	}
	//插入一条新的单词记录
	void insert(char *s)
	{
		int u=0,len=strlen(s);
		for(int i=0;i<len;i++)
		{
			int c=(s[i]-'a');
			//如果该节点还不存在，创建该节点
			if(!ch[u][c])
			{
				memset(ch[sz],0,sizeof(ch[sz]));
				val[sz]=0;
				//为该节点分配编号
				ch[u][c]=sz++;
			}
			//向下移
			u=ch[u][c];
		}
		val[u]++;
	}
	//查询该记录
	int query(char *s)
	{
		int len=strlen(s),u=0,c,res=0;
		for(int i=0;i<len;i++)
		{
		   c=s[i]-'a';
		   if(ch[u][c])
		   {
			   //其实因为a的查询是以a的起始位置不断后移的
			   //这是从a往后不同长度匹配b
			   u=ch[u][c];
			   res+=val[u];
		   }
		   else 
			   return res;
		}
		return res;
	}
};
Trie T;
char a[100005][10010];
char ss[10010];
int main()
{
    int n,m,t,len,ans;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		//初始化
		T.init();
		//先将a读入并存下来
        for(int i=0;i<n;i++)
		{
			getchar();
			scanf("%s",a[i]);
		}
		//用b构建字典树
		for(int i=0;i<m;i++)
		{
			getchar();
			scanf("%s",ss);
			T.insert(ss);
		}
		//以a的不同起始位置取查询结果
		for(int i=0;i<n;i++)
		{
			len=strlen(a[i]);
			ans=0;
			for(int j=0;j<len;j++)
			{
               ans+=T.query(a[i]+j);
			}
			printf("%dn",ans);
		}
	}
	return 0;
}