题目大意 看输入的每个字符串中是否有一个字符串是另一个字符串的前缀
#include<iostream> #include<cstring> #include<algorithm> #include<string.h> #include<stdio.h> using namespace std; #define maxn 10001 string b[maxn]; ; struct ac{ ]; void init(){ sum=;fa=; memset(nex,,sizeof(nex)); } }tre[maxn*]; void add(char a[],bool &f){ ,j=,k=; while(a[i]){ '; if(tre[k].nex[z]){ j=tre[k].nex[z]; tre[j].sum++; ; }else{ tre[k].nex[z]=++tot; j=tot; tre[j].init(); tre[j].sum++; } k=j; i++; } tre[k].fa++; } /*bool query(string a){ int i=0,j=0,k=0; while(i<a.size()-1){ int z=a[i]-'0'; if(tre[k].nex[z]){ j=tre[k].nex[z]; if(tre[j].fa) return 1; }else return 0; k=j; i++; } }*/ int main(){ ]; ,tt=; ; while(scanf("%s",a)!=EOF){ ]!='){ add(a,fa); }else{ if(fa) printf("Set %d is not immediately decodable\n",tt++); if(!fa){ printf("Set %d is immediately decodable\n",tt++); } len=;tot=,fa=; memset(tre,,sizeof(tre)); } } }
题目链接 : POJ--3630 Phone List
题意和上一个题差不多 都是找里面是否含有前缀和相同的
#include<iostream> #include<cstring> #include<algorithm> #include<string.h> #include<stdio.h> using namespace std; #define maxn 100010 ; struct ac{ ]; void init(){ sum=;fa=; memset(nex,,sizeof(nex)); } }tre[maxn]; void add(char a[],bool &f){ ,j=,k=; while(a[i]){ '; if(tre[k].nex[z]){ j=tre[k].nex[z]; tre[j].sum++; ) f=; ; }else{ tre[k].nex[z]=++tot; j=tot; tre[j].init(); tre[j].sum++; } k=j; i++; } tre[k].fa++; } /*bool query(string a){ int i=0,j=0,k=0; while(i<a.size()-1){ int z=a[i]-'0'; if(tre[k].nex[z]){ j=tre[k].nex[z]; if(tre[j].fa) return 1; }else return 0; k=j; i++; } }*/ ]; int main(){ int t; cin>>t; while(t--){ int n; scanf("%d",&n); memset(tre,,sizeof(tre)); tot=; ; ;j<n;j++){ scanf("%s",a); if(!fa) add(a,fa); } if(fa){ printf("NO\n"); }else{ printf("YES\n"); } } }