自动搬运

查看原文

来自洛谷，原作者为

	Ervin **

搬运于2025-08-24 21:53:40，当前版本为作者最后更新于2018-03-17 15:16:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题看一眼就知道这是个$STL$库里的$map$

• 但是。。
• 神犇我选择了$Trie$树，$Hahahaha...$
• 可能没有$dalao$发这个题目的$Trie$树题解是因为太麻烦了、、、不过$A+B$ $Problen$都有发各种看不懂的题解的人，我发个$Trie$树也没有什么说不过去的吧、、

$*******$ $dalao$ 专用分割线$******$

可能有的小朋友们还不知道$Trie$树是什么(虽然我也是刚刚才知道)，我还是先讲一下$Trie$树吧。。

$To$ $begin$ $with$，需要了解一下$Trie$树是干什么的，$Trie$树又叫做字典树。字典，就是用来查字的，顾名思义，$Trie$树也是用来查字或者单词的。

那什么时候会用到$Trie$树呢？

举个例子吧：

1. 就像这道题目一样，查寻这个单词在一句话中出现还是没有出现，非常简单么，$map$啊，短小精干
2. 但是，如果给出$n$个单词和$m$组询问，询问是多少个单词的前缀，那么$map$的话就完美的$TLE$了，这个时候就要使用久违的$Trie$树了！！

$Second$，先模拟一下$Trie$树的各种操作吧。

如果要插入

$CAI,CHANG,CHAO,CHEN,LAN,LI,LIU,LONG,$

$WANG,WEN,WU,YANG,YUN,ZHAO$这些字符，

所建出的$Trie$树就是这样的。

呈上图来：

注意：$Trie$树的根节点是空的，然后在单词的末尾有个标记，这点事必不可少的。

$Then$，介绍一下$Trie$树的基本操作吧。

$A.$ $Insert$插入：

1. 首先要给所有的字母一个编号，其实并不用从$a...z$全部都编号，你会发现其实有很多字母是用不到的，所以只需要判断树中有没有这个单词的前缀，然后进行编号。
2. 编号完成后更新当前位置，接着进入下一个层。

代码统一在后边统一粘上

$B.$ $Check$查询： 从$Trie$树的根开始，看有没有当前的字符，如果没有，就直接$break$掉，否则就跟新当前位置，进入下一层。

其实$Trie$树的常用操作就这两个，其实$Trie$树涉及的题目也不算很多，其实学习$Trie$树还可以为以后的$AC$自动机(就是用了这个算法就可以自动AC了)做一下铺垫。

好了，对于$Trie$树的介绍就到这里吧，下面就说这个题目了，其实这个题目就是一道裸裸的$Trie$树模板，写出上边介绍的两个操作，再加上点高深的东西就可以$AC$了。

下边直接粘代码吧：

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
char s[10010];
int nex[500010][26],n,cnt=0;
bool b[500010][1010];
inline int read()
{
    int k=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
    while(ch>='0'&&ch<='9')
	{
		k=k*10+ch-'0';
		ch=getchar();
	}
    return k*f;
}
inline void insert(int x)
{
    scanf("%s",s+1);
	int l=strlen(s+1);
    int now=0;
    for(int i=1;i<=l;i++)
	{
        int p=s[i]-'a';
        if(!nex[now][p])         //如果$Trie$树中没有这个单词的前缀就进行编号
			nex[now][p]=++cnt;   //上文中说到的编号 
        now=nex[now][p];         //接着深入一层，更新现在的位置 
    }
    b[now][x]=1;                 //这个单词在第x行出现了
}
inline void check()
{
    scanf("%s",s+1);
	int l=strlen(s+1);
    int now=0,flag=1;
    for(int i=1;i<=l;i++)
	{
        int p=s[i]-'a';
        if(!nex[now][p])         //如果在Trie树中没有当前的字符，就可以直接break掉了 
		{
			flag=0;
			break;
		}
        now=nex[now][p];         //否则就更新位置 
    }
    if(flag)
		for(int i=1;i<=n;i++)    //题面上说按字典序输出 
			if(b[now][i])
				printf("%d ",i); //输出在哪些句子中出现过 
    puts("");                    //相当于printf("\n");其实这个条件很容易看不到，一定要注意啊！！ 
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
	{
        int x=read();
        for(int j=1;j<=x;j++)    //一个单词一个单词的插入Trie树里 
			insert(i);
    }
    int m=read();
    for(int i=1;i<=m;i++)
		check();
    return 0;
}

感谢大家的观看，上方点赞哦!!