自动搬运

查看原文

来自洛谷，原作者为

	Atserckcn 愿你的刀仍然锋利

搬运于2025-08-24 22:58:15，当前版本为作者最后更新于2024-05-26 20:00:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P10470 前缀统计题解

题目简述：

一共有 $N$ 个字符串 $S_1,S_2,\cdots,S_N$，有 $M$ 次询问，每次给定字符串 $T$，需要求出 $N$ 个字符串中一共有多少个字符是 $T$ 的前缀。

数据范围：

总长度不超过 $10^6$。

思路1：

运用 STL 函数中的 find() 函数，每次查找 $N$ 个字符串，并计算其 find() 函数返回值为 $0$，即是 $T$ 的前缀的情况数。

但是分析一下时间复杂度，我们会发现，$N$ 和 $M$ 最大都为 $10^5$，则每次匹配的最坏结果就是 $10^5 \times 10^5 =10^{10}$，很显然会时间超限。

那么我们需要认识一种新的数据结构——字典树！

trie 树

字典树（trie 树）是一种用于实现字符串快速检索的多叉树结构。

trie 树的每个节点都拥有若干个字符指针，若在插入或检索字符串时扫描到一个字符 c，就沿着当前节点的 c 字符指针，走向该指针指向的节点。

下图即为一个简易版字典树，存储了单词：ab、ac、ba。

那么该如何用代码实现字典树呢？

像以往的树形结构一样，我们可以用结构体存树：

struct EDGE{
	int son[26];//因为保证只有小写字母，所以分支最多有26个
	int cnt;//统计到这个节点为止，一共有几个前缀
}edge[MAXN];

当然，因为输入的是小写字母，但是结构体里边是数字的一维数组，所以我们还要手打一个字符串转数字的函数——

int getnumber(char ch)//蒟蒻不会用map，勿喷
{
	return ch-'a';//ASCII码值
}

接下来，我们需要解决两大问题：

1、如何将一个字符串插入字典树？

思路：由于字典树是用来存字符的，所以我们可以将整个字符串转为一个个字符，再将其插入字典树，具体操作注释在代码中。

void insert(string s)//插入字符串s
{
	now=1;//相当于一个起点
	for(int i=0;i<s.size();i++)//分解每个字符
	{
		num=getnumber(s[i]);//转化
		if(!edge[now].son[num])//如果当前字典树不存在此单词
			edge[now].son[num]=++cnt;//加边
		now=edge[now].son[num];//沿着现在的这条边走
		if(i==s.size()-1) edge[now].cnt++;//特判情况，若已经是字符串的最后一个字符，则代表字典树的这个节点是一个单词的末尾，统计的cnt需要+1
	}
	return;
}

2、如何统计一个字符串前缀的个数？

思路：顺着查找字符串的每个字符，一路顺着字典树，直到查完，一路上统计 cnt 个数。

Code:

void find(string s)//统计字符串s的前缀数量
{
	ans=0;//统计的变量
	now=1;//起点
	for(int i=0;i<s.size();i++)
	{
		num=getnumber(s[i]);
		if(!edge[now].son[num])//如果到头了
		{
			printf("%d\n",ans);
			return;
		}
		now=edge[now].son[num];//转移
		ans+=edge[now].cnt;//统计
	}
	printf("%d\n",ans);
	return;
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int now,cnt=1,num,ans;
int getnumber(char ch)
{
	return ch-'a';
}
struct EDGE{
	int son[26];
	int cnt;
}edge[MAXN];
int n,m;
string s;
void insert(string s)
{
	now=1;
	for(int i=0;i<s.size();i++)
	{
		num=getnumber(s[i]);
		if(!edge[now].son[num])
			edge[now].son[num]=++cnt;
		now=edge[now].son[num];
		if(i==s.size()-1) edge[now].cnt++;
	}
	return;
}
void find(string s)
{
	ans=0;
	now=1;
	for(int i=0;i<s.size();i++)
	{
		num=getnumber(s[i]);
		if(!edge[now].son[num])
		{
			printf("%d\n",ans);
			return;
		}
		now=edge[now].son[num];
		ans+=edge[now].cnt;
	}
	printf("%d\n",ans);
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		cin >> s;
		insert(s);
	}
	for(int i=1;i<=m;i++)
	{
		cin>>s;
		find(s);
	}
	return 0;
}

AC 记录

推荐关联题目：P8306 【模板】字典树，以及我写的个人记录题解。