首页 > 代码库 > hdu 1251
hdu 1251
统计难题
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others)Total Submission(s): 16960 Accepted Submission(s): 7304
Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana band bee absolute acm ba b band abc
Sample Output
2 3 1 0
A字典树的第一道题
#include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <string> using namespace std; struct edge{ int u , v , letter , sum; edge(int a = 0 , int b = 0 , int c = 0 , int d = 0){ u = a , v = b , letter = c , sum = d; } }; vector<edge> e; vector<int> head , next; void add(int u , int v , int letter , int sum){ e.push_back(edge(u , v , letter , sum)); next.push_back(head[u]); head[u] = next.size()-1; head.push_back(-1); } void addLibrary(string s){ int u = 0 , index = 0; while(index < s.length()){ int Next = head[u]; while(Next != -1){ if(e[Next].letter == s[index]-'a') break; Next = next[Next]; } if(Next == -1) break; e[Next].sum++; index++; u = e[Next].v; } while(index < s.length()){ add(u , head.size() , s[index]-'a' , 1); index++; u = head.size()-1; } } int query(string s){ int u = 0 , index = 0 , Next; while(index < s.length()){ Next = head[u]; while(Next != -1){ if(e[Next].letter == s[index]-'a') break; Next = next[Next]; } if(Next == -1) return 0; index++; u = e[Next].v; } return e[Next].sum; } int main(){ string dic; head.push_back(-1); while(getline(cin , dic)){ if(dic.length() == 0) break; addLibrary(dic); } while(cin >> dic){ printf("%d\n" , query(dic)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。