首页 > 代码库 > POJ 1056 IMMEDIATE DECODABILITY Trie 字符串前缀查找
POJ 1056 IMMEDIATE DECODABILITY Trie 字符串前缀查找
POJ1056
给定若干个字符串的集合 判断每个集合中是否有某个字符串是其他某个字符串的前缀
(哈夫曼编码有这个要求)
简单的过一遍Trie就可以了
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<vector> #include<queue> #include<algorithm> using namespace std; const int maxl=1e+4,maxc=2,BASE=‘0‘; struct Trie { int tot,root,child[maxl][maxc]; bool flag[maxl]; Trie() { memset(child[1],0,sizeof(child[1])); flag[1]=false; root=tot=1; } void insert(const char * str) { int *cur=&root; for(const char *p=str;*p;++p) { cur=&child[*cur][*p-BASE]; if(*cur==0) { *cur=++tot; memset(child[tot],0,sizeof(child[tot])); flag[tot]=false; } } flag[*cur]=true; } bool query(const char *str) { int *cur=&root; const char *p; for(p=str;*p&&*cur;++p) { cur=&child[*cur][*p-BASE]; if(flag[*cur]==true)return false; } if((*cur==0))return true; if(!(*p))return false; else return true; } }; int main() { bool flagg; int tott=0; do { tott++; flagg=false; Trie tr; char c[1000]; bool ans=true; int len=0; while(true) { char nowc=getchar(); if(nowc==EOF)return 0; if(nowc==‘9‘){flagg=true;getchar();break;} if(nowc!=‘\n‘)c[len++]=nowc; else { c[len++]=‘\0‘; if(!tr.query(c)){ans=false;} tr.insert(c); len=0;continue; } } if(ans){printf("Set %d is immediately decodable\n",tott);} else {printf("Set %d is not immediately decodable\n",tott);} } while(flagg); return 0; }
POJ 1056 IMMEDIATE DECODABILITY Trie 字符串前缀查找
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。