字典树

hdu 1251 统计难题

字典树模板题。

#include <bits/stdc++.h> using namespace std; const int N=1e6+10;//开大一点，否则RE char s[N]; int num,cnt[N],ch[N][30]; void build(char s[]) { int u=0; for(int i=0;i<strlen(s);i++) { int x=s[i]-'a'; if(!ch[u][x])ch[u][x]=++num; u=ch[u][x]; cnt[u]++; } } int query(char s[]) { int u=0; for(int i=0;i<strlen(s);i++) { int x=s[i]-'a'; if(!ch[u][x])return 0; u=ch[u][x]; } return cnt[u]; } int main() { ios::sync_with_stdio(false); while(gets(s)&&s[0]!='\0')//用gets处理空行，如果是空行，gets会自动把'\n'转化为'\0' build(s); while(gets(s)&&s[0]!='\0')printf("%d\n",query(s)); //虽然是处理到文件末尾，但是不能写成while(cin>>s)，否则会WA(不知道为什么...) return 0; }

hdu 1671 Phone List

给你n个字符串，如果存在一个字符串是其他某个字符串的前缀，则输出NO，否则输出YES。

#include <bits/stdc++.h> using namespace std; const int N=1e4+10,M=1e5+10; string a[N]; int t,n,num,cnt[M],ch[M][10]; bool cmp(string s1,string s2) {return s1<s2;} int build(string s) { int u=0; for(int i=0;i<s.length();i++) { int x=s[i]-'0'; if(cnt[u])return 1; if(!ch[u][x])ch[u][x]=++num; u=ch[u][x]; } cnt[u]++; return 0; } int main() { ios::sync_with_stdio(false); cin>>t; while(t--) { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1,cmp); memset(ch,0,sizeof(ch)); memset(cnt,0,sizeof(cnt)); num=0; int flag=0; for(int i=1;i<=n;i++) { int tmp=build(a[i]); if(tmp==1){printf("NO\n");flag=1;break;} } if(flag==0)printf("YES\n"); } return 0; }

hdu 2072 单词数

分割单词，再构造字典树即可。 注意特判 全是空格 的情况。

要注意一下输入字符串的格式。

跳过空格输入可以用 gets(a) 或者 scanf("%[^\n]",a)

while(scanf("%[^\n]",a))无法while循环，因为第一次遇到 \n 程序就停止了。

可以写 while(scanf("%[^\n]%*c",a))， 与 while(gets(a)) 等效。 %*c表示跳过一个字符，也就是把 \n 吸收掉。

也可以写 while(scanf("%[^\n]",a))，内循环加一句 getchar() 来吸收 \n 字符。

（所以说为什么不直接写gets(a)？）

关于while(scanf("%[^\n]%*c",a))输入，具体的原理可以看看这篇文章：https://blog.csdn.net/weixin_43469047/article/details/83753526

#include <bits/stdc++.h> using namespace std; const int N=1e5+10; char a[N],s[N]; int num,tot,ans,cnt[N],ch[N][30]; void build(char s[]) { int u=0; for(int i=1;i<=tot;i++) { int x=s[i]-'a'; if(!ch[u][x])ch[u][x]=++num; u=ch[u][x]; } cnt[u]++; if(cnt[u]==1)ans++; } int main() { ios::sync_with_stdio(false); while(gets(a)&&a[0]!='#')//注意用gets(a)，不要用scanf(" %[^\n]",a)，否则会错 { memset(s,0,sizeof(s)); memset(ch,0,sizeof(ch)); memset(cnt,0,sizeof(cnt)); tot=0;num=0;ans=0; for(int i=0;i<strlen(a);i++) { if(a[i]!=' ') { s[++tot]=a[i]; if(a[i+1]==' '||a[i+1]=='\0') { build(s); memset(s,0,sizeof(s)); tot=0; } } } printf("%d\n",ans); } return 0; }