题意：给你一些字符串，要你判断有没有其中的一个字符串是另外一个字符串的前缀。
题解：字典树解决。
AC代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef __int64 LL; const int N=2; const LL mod=1000000007LL; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); char s[15]; struct Trie { Trie *next[N]; int v; Trie() { v=1; for(int i=0;inext[i] = NULL; } void createTrie(char *str) { int i,j,id; int len=strlen(str); Trie *p=root,*m; for(i=0;inext[id]==NULL) { p->next[id]=new Trie(); p=p->next[id]; } else { p=p->next[id]; } } p->v++; } int findTrie(char *str) { int i,id; int len=strlen(str); Trie *p=root; for(i=0;inext[id]; if(p==NULL) //若为空集，表示不存以此为前缀的串 return 0; } return p->v; //此串是字符集中某串的前缀,这个地方可能要判断是否在结尾节点 } void dealTrie(Trie *T) {//若果有多组数据-多棵树，那么要释放内纯 int i; if(T==NULL) return ; for(i=0;inext[i]!=NULL) dealTrie(T->next[i]); free(T);//释放 } int flag; void dfs(Trie *Tr) { if(flag) return ; if(Tr->v>1&&(Tr->next[0]!=NULL||Tr->next[1]!=NULL)) { flag=1; return ; } for(int i=0;i<2;i++) { if(Tr->next[i]==NULL) continue; dfs(Tr->next[i]); } } int main() { int i,j,p=1,ca=0; while(scanf("%s",s)!=EOF) { if(p) root=new Trie(); if(strcmp(s,"9")!=0) { createTrie(s); p=0; } else { flag=0; dfs(root); if(flag) printf("Set %d is not immediately decodable\n",++ca); else printf("Set %d is immediately decodable\n",++ca); dealTrie(root); p=1; } } return 0; } #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef __int64 LL; const int N=2; const LL mod=1000000007LL; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); char s[15]; struct Trie { Trie *next[N]; int v; Trie() { v=1; for(int i=0;inext[i] = NULL; } void createTrie(char *str) { int i,j,id; int len=strlen(str); Trie *p=root,*m; for(i=0;inext[id]==NULL) { p->next[id]=new Trie(); p=p->next[id]; } else { p=p->next[id]; } } p->v++; } int findTrie(char *str) { int i,id; int len=strlen(str); Trie *p=root; for(i=0;inext[id]; if(p==NULL) //若为空集，表示不存以此为前缀的串 return 0; } return p->v; //此串是字符集中某串的前缀,这个地方可能要判断是否在结尾节点 } void dealTrie(Trie *T) {//若果有多组数据-多棵树，那么要释放内纯 int i; if(T==NULL) return ; for(i=0;inext[i]!=NULL) dealTrie(T->next[i]); free(T);//释放 } int flag; void dfs(Trie *Tr) { if(flag) return ; if(Tr->v>1&&(Tr->next[0]!=NULL||Tr->next[1]!=NULL)) { flag=1; return ; } for(int i=0;i<2;i++) { if(Tr->next[i]==NULL) continue; dfs(Tr->next[i]); } } int main() { int i,j,p=1,ca=0; while(scanf("%s",s)!=EOF) { if(p) root=new Trie(); if(strcmp(s,"9")!=0) { createTrie(s); p=0; } else { flag=0; dfs(root); if(flag) printf("Set %d is not immediately decodable\n",++ca); else printf("Set %d is immediately decodable\n",++ca); dealTrie(root); p=1; } } return 0; }