首页 > 代码库 > Trie树 POJ1056 IMMEDIATE DECODABILITY
Trie树 POJ1056 IMMEDIATE DECODABILITY
题目:http://poj.org/problem?id=1056
题意:判断是否有串是其他串的前缀
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include<algorithm> #include<stdio.h> #include<iostream> #include<set> #include<map> #include<queue> #include<stack> #include<string.h> using namespace std; struct Node { int cnt;Node * next[50]; }e[111111]; int len=0; Node * newnode() { memset (&e[len],0, sizeof (e[len])); return &e[len++]; } void Insert( char *s,Node *root) { int len= strlen (s); for ( int i=0;i<len;i++){ int cc=s[i]- ‘0‘ ; if (!root->next[cc]){ root->next[cc]=newnode(); } root->cnt++; root=root->next[cc]; } root->cnt++; } int Find( char *s,Node *root) { int len= strlen (s); for ( int i=0;i<len;i++){ int cc=s[i]- ‘0‘ ; root=root->next[cc]; } if (root->cnt>1) return 1; else return 0; } char str[1005][1005]; int main() { int i=-1; int ret=1; int flag=0;Node *root=newnode(); while ( scanf ( "%s" ,&str[++i])!=EOF){ Insert(str[i],root); if ( strcmp (str[i], "9" )==0){ for ( int j=0;j<i;j++){ if (Find(str[j],root)){ flag=1; printf ( "Set %d is not immediately decodable\n" ,ret++); break ; } } if (flag==0){ printf ( "Set %d is immediately decodable\n" ,ret++); } i=-1;len=0;flag=0;root=newnode(); } } return 0; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。