Adament Cabin

  • 计算机
    • Algorithm
    • Linux
    • Problems
    • AI
  • 日语学习
  • ACG
    • 追番列表
    • 游戏
  • 常日说
  • 杂物
    • 资料
    • 资源
    • 治疗中心
  • ao的链接
  • 分站
  • Chinese
    • Japanese
Adament Cabin
恋厨综合症第二治疗中心
  1. 首页
  2. 计算机
  3. Problems
  4. 正文

HDU-1251 统计难题

2022年8月10日 1059点热度 0人点赞 1条评论

Problem-1251

Problem Description

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

Output

对于每个提问,给出以该字符串为前缀的单词的数量.

Sample Input

banana
band
bee
absolute
acm

ba
b
band
abc

Sample Output

2
3
1
0

Author

Ignatius.L

使用字典树(Trie)存储字符数据。在Oi-wiki上的字典树模板是:

Oi-Wiki上的图
struct trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int l) {  // 插入字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有,就添加结点
      p = nex[p][c];
    }
    exist[p] = 1;
  }

  bool find(char *s, int l) {  // 查找字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};

字典树就是把一串字符串摁拆了然后以树的结构储存。在模板中,nex[p][c],p是改节点的下标即cnt,c是字母代号,其值表示下一个节点代号。

样图中1->2的nex即为nex[1][0]=2,0的含义是a。4->9的nex即为nex[4][1]=9。

本题要求的是查找前缀,其实就是寻求树节点所支配的所有叶子。

如图所示,用Calc数组来存储改节点下的所有叶子。其实换一种想法,可以用遍历时路过该节点的次数作为此节点Calc数组。

如这个数据:

acm
ac
acj
ack
abc
abd

在这个数据的字典树Insert过程中,可以看到a走了6次,b被路过了2次,c被路过了4次。

这其实就是以a,ab,ac作为输入时的答案。

因此,需要将模板代码改成如下形式:

int nex[1000005][26],cnt;
int calc[1000005];
void insert(string str){
    int p=0;
    for(int i=0;i<str.size();i++){
        int ch=str[i]-'a';
        if(!nex[p][ch]) {
            nex[p][ch]=++cnt;
        }
        p=nex[p][ch];
        calc[p]++;//储存遍历的时候该节点路过了几次
    }
}
int find(string str){
    int p=0;
    for(int i=0;i<str.size();i++){
        int ch=str[i]-'a';
        if(!nex[p][ch]) return 0;
        p=nex[p][ch];
    }
    return calc[p];//直接返回calc值,此时exist的作用被calc代替。
}
#include <iostream>
#include <cstring>
using namespace std;
int nex[1000005][26],cnt;
int calc[1000005];
void insert(string str){
    int p=0;
    for(int i=0;i<str.size();i++){
        int ch=str[i]-'a';
        if(!nex[p][ch]) {
            nex[p][ch]=++cnt;
        }
        p=nex[p][ch];
        calc[p]++;
    }
}
int find(string str){
    int p=0;
    for(int i=0;i<str.size();i++){
        int ch=str[i]-'a';
        if(!nex[p][ch]) return 0;
        p=nex[p][ch];
    }
    return calc[p];
}
int main(){
//    freopen("In.txt","r",stdin);
    string str;
    memset(nex,0,sizeof nex);
    while(getline(cin,str)){
        if(str=="") break;
        insert(str);
    }
    while(getline(cin,str)){
        cout << find(str) << endl;
    }
    return 0;
}
标签: C/C++/C#
最后更新:2022年8月11日

BiyiAdopac

是铁龙鸣。

点赞
< 上一篇
下一篇 >

文章评论

  • 蜡笔小金QAQ

    这个版面好高级 (⊙o⊙)

    2022年8月15日
    回复
  • razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
    取消回复

    分类
    • AI / 1篇
    • Algorithm / 5篇
    • Linux / 6篇
    • Problems / 3篇
    • 常日说 / 1篇
    • 日本語 / 2篇
    • 游戏 / 1篇
    • 计算机 / 14篇
    • 资料 / 4篇
    标签聚合
    Learning AI ArchLinux Physics Arcaea LaTex C/C++/C# Magisk
    The World of Scarlet
    https://www.adament.xyz/wp-content/uploads/2024/10/the-world-of-scarlet-Piano.mp3

    COPYRIGHT © 2025 adament.xyz. ALL RIGHTS RESERVED.
    本站虽然不重要但是还是有的 隐私政策