Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others) Total Submission(s): 38793 Accepted Submission(s): 14167
Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana band bee absolute acm ba b band abc
Sample Output
2 3 1 0
法一：指针做法（这道题会爆内存）
#include <bits/stdc++.h> using namespace std; #define mst(a,b) memset((a),(b),sizeof(a)) #define f(i,a,b) for(int i=(a);i<=(b);++i) const int maxn = 26; const int mod = 1e9+7; const int INF = 1e9; #define ll long long #define rush() int T;scanf("%d",&T);while(T--) struct Trie { int v; Trie *next[maxn]; }; Trie *root; void createTrie(char *str) { int len=strlen(str); Trie *p=root,*q; for(int i=0; i<len; i++) { int id=str[i]-'a'; if(p->next[id]==NULL) { q=(Trie*)malloc(sizeof(Trie)); q->v=1; for(int j=0; j<maxn; j++) q->next[j]=NULL; p->next[id]=q; p=p->next[id]; } else { p->next[id]->v++; p=p->next[id]; } } } int findTrie(char*str) { int len=strlen(str); Trie *p=root; for(int i=0;i<len;i++) { int id=str[i]-'a'; p=p->next[id]; if(p==NULL) return 0; } return p->v; } int dealTrie(Trie *t) { if(t==NULL) return 0; for(int i=0;i<maxn;i++) { if(t->next[i]!=NULL) dealTrie(t->next[i]); } free(t); return 0; } int main() { char str[15]; root=(Trie*)malloc(sizeof(Trie)); for(int i=0;i<maxn;i++) root->next[i]=NULL; while(gets(str)&&str[0]!='\0') createTrie(str); while(~scanf(" %s",str)) { int sum=findTrie(str); printf("%d\n",sum); } dealTrie(root); return 0; }
法二：数组做法
#include <cstdio> #include <cassert> #include <queue> #include <cstring> #include <algorithm> using namespace std; #define mst(a,b) memset((a),(b),sizeof(a)) #define rush() int T;scanf("%d",&T);while(T--) typedef long long ll; const int maxn = 30; const ll mod = 1e9+7; const int INF = 0x3f3f3f3f; const double eps = 1e-9; int sz; int ch[400010][maxn]; //前者大于2^26 int word[400010]; int val[400010]; void init() { sz=1,mst(val,0); mst(ch[0],0),mst(word,0); } void insert(char *s) { int len=strlen(s); int u=0; for(int i=0;i<len;i++) { int c=s[i]-'a'; if(!ch[u][c]) //节点不存在 { mst(ch[sz],0); ch[u][c]=sz++; //节点数加1 } u=ch[u][c]; word[u]++; //单词数加1 } val[u]=1; //标记单词节点 } int find(char *s) //查询以s为前缀的单词有几个 { int len=strlen(s); int u=0; for(int i=0;i<len;i++) { int c=s[i]-'a'; if(!ch[u][c]) return 0; u=ch[u][c]; } return word[u]; } void find_pre(char *s) //查找并输出字符串在串集里面唯一确定的最短前缀 { int len=strlen(s); int u=0; vector<char>vec; int flag=0; for(int i=0;i<len;i++) { int c=s[i]-'a'; u=ch[u][c]; vec.push_back(s[i]); if(word[u]==1) { flag=1; break; } } if(flag==0) return; for(auto it :vec) { printf("%c",it); } puts(""); } char s[15]; int main() { init(); while(gets(s)&&s[0]!='\0') { insert(s); } while(~scanf("%s",s)) { int ans=find(s); printf("%d\n",ans); } return 0; }
