在连续用STL水过了P3879 阅读理解和P5149 会议座位后决定好好用字典树做道题(～￣▽￣)～

什么是字典树？

 　　在处理字符串问题时，有两个基础操作：存储和查询。而一个字串(单词)在只包含26个英文字母(不区分大小写)的情况下，与其它字串经常会出现重叠部分。如果能把这些重叠部分集中起来去重，既可以节省空间，也可以缩短查询时间(不用每出现一次都比对一次)。于是，就有不知是谁想到了树这个结构。

 　　我们来看一个例子：要依次添加三个字串aab,aac,bac
 　　首先，我们将第一个字串以链的形式存起来

 　　接着我们看第二个字串aac，发现它和第一个字串有公共前缀aa，于是我们可以直接在第二个a后插入一个c,而不需要把重叠部分再存一遍。此时，这个图就变成了一棵树

 　　可插入第三个字串时问题来了，它与第二个字串有公共部分ac，难道我们要在第二个a前插入一个新前缀b吗？显然不行，因为那样我们维护的就不是一棵树了；具体地说，我们插入新字串的方法其实是从根节点开始一个一个比对寻找与之前字串的公共前缀，直到不再有公共部分时就将后面的新添加成一条分支。那此时完全没有公共前缀，不是要新建一棵树吗？其实，我们可以在最前段放置一个空的根节点，以便统一成一棵树

 　　于是一颗字典树就建成了。
 　　查询方法很类似，也是从根节点开始一一比对，先不再多说。

 　　回到本题，一看到公共前缀，显然就是针对字典树的，而且它还没有26个字母，只有0和1两个数字。存一颗字典树的方法有很多，大佬们喜欢用指针、结构体什么的，这道题我就使用相对简单的数组来存。

 　　这题的意思其实就是给一个新的字串，求已知字串中以新字串为前缀，或是新字串的前缀的有多少。我们用$book_i$记录经过节点$i$的字串数，$end_i$记录以$i$为结尾的字串数，则在字典树中查询新字串时加上沿途的$end$，最后再加上$book_i$-$end_i$即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int m,n,l,x,trie[500005][2],book[500005],end[500005],tot,now,cnt,flag;
//trie存储字典树，trie[i][x](x=0或1)表示节点i的后继为x的节点编号 
int main()
{
	scanf("%d%d",&m,&n);
	memset(trie,-1,sizeof(trie));
	//trie[i][x]==-1则表示节点i没有后继x 
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&l);now=0;
		//now表示当前节点，每次从根节点开始 
		for(int j=1;j<=l;j++) 
		{
			scanf("%d",&x);
			if(trie[now][x]==-1) trie[now][x]=++tot;
			//如果节点i没有后继x，则新插入节点i的后继x，编号为tot 
			now=trie[now][x];
			if(j==l) end[now]++; 
			book[now]++;
		}
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&l);now=cnt=flag=0;
		for(int j=1;j<=l;j++)
		{
			scanf("%d",&x);
			if(flag) continue;
			if(trie[now][x]==-1)
			{
				printf("%d\n",cnt);
				flag=1;continue;
				//如果从now开始不再有公共部分了就可以直接输出，并且绝没有以这个新字串为前缀的已知字串 
			}
			now=trie[now][x];
			//不然继续往下 
			cnt+=end[now];
			if(j==l) printf("%d\n",cnt+book[now]-end[now]);
			//如果全部都比对上了，说明新字串是某些已知字串的前缀 
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=5110000;
int id,ch[N][2],a[N],ed[N],ed2[N];
void ins()
{
	int p=0;
	for(int i=1;i<=a[0];i++)
	{
		int j=a[i];
		if(!ch[p][j])ch[p][j]=++id;
		p=ch[p][j];	
		ed2[p]++;//ed2表示前缀的存在 
	}
	ed[p]++;//ed表示完成的一条信息的存在 
}
int query()
{
	int p=0,ret=0;
	for(int i=1;i<=a[0];i++)
	{
		int j=a[i];
		if(!ch[p][j])return ret;
		p=ch[p][j];
		ret+=ed[p];
	}
	return ret+ed2[ch[p][0]]+ed2[ch[p][1]]; 
	//为什么不是return ret+ed2[p]?  因为每天信息都是自己的前缀，要避免重复计算 
}
int main()
{
	int n,m;scanf("%d%d", &n, &m);
	id=0;memset(ch,0,sizeof(ch));memset(ed,0,sizeof(ed));
	memset(ed2,0,sizeof(ed2));
	for(int i=1;i<=n;i++)
	{
		scanf("%d", &a[0]);for(int j=1;j<=a[0];j++) scanf("%d", &a[j]);
		ins();
	}
	
	for(int i=1;i<=m;i++)
	{
		scanf("%d", &a[0]);for(int j=1;j<=a[0];j++) scanf("%d", &a[j]);
		printf("%d\n", query());
	}
	
	return 0;
}