题解：P10470 前缀统计

· · 题解

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 【模板】字典树，以及我写的个人记录题解。