首页 > 代码库 > No Prefix Set(Tire Tree)
No Prefix Set(Tire Tree)
Given strings. Each string contains only lowercase letters from (both inclusive). The set of strings is said to be GOOD SET if no string is prefix of another string else, it is BAD SET. (If two strings are identical, they are considered prefixes of each other.)
For example, aab, abcde, aabcd is BAD SET because aab is prefix of aabcd.
Print GOOD SET if it satisfies the problem requirement. Else, print BAD SET and the first string for which the condition fails.
Input Format First line contains , the number of strings in the set. Then next lines follow, where line contains string.
Constraints Length of the string
Output Format Output GOOD SET if the set is valid. Else, output BAD SET followed by the first string for which the condition fails.
Sample Input00
7aabdefgababcdeaabcdecedaaabbbbbbbbbbjabjjjad
Sample Output00
BAD SETaabcde
Sample Input01
4aabaacaacghghaabghgh
Sample Output01
BAD SETaacghgh
Explanation aab is prefix of aabcde. So set is BAD SET and it fails at string aabcde.
Code:
1 #pragma comment(linker, "/STACK:36777216") 2 3 #include <bits/stdc++.h> 4 using namespace std; 5 #define LSON id << 1 , l , mid 6 #define RSON id << 1 | 1 , mid + 1 , r 7 #define ROOT 1 , 1 , n 8 #define CLR(x , y) memset(x , y , sizeof(x)) 9 #define LOWBIT(x) x & (-x) 10 #define FORN(i , a , n) for(int i = (a) ; i <= (n) ; ++i) 11 #define FORP(i , n , a) for(int i = (n) ; i >= (a) ; --i) 12 #define CASE(x) printf("Case %d: ", x) 13 #define SFD(x) scanf("%lf" , &x) 14 #define SFC(x) scanf(" %c" , &x) 15 #define SFS(x) scanf(" %s" , x) 16 #define SFI(x) scanf("%d" , &x) 17 #define SFL(x) scanf("%lld" , &x) 18 #define SFI64(x) scanf("%I64d" , &x) 19 #define PFF(x) printf("%f" , x) 20 #define PFD(x) printf("%lf" , x) 21 #define PFI(x) printf("%d" , x) 22 #define PFC(x) printf("%c" , x) 23 #define PFS(x) printf("%s" , x) 24 #define PFI64(x) printf("%I64d" , x) 25 #define PFL(x) printf("%lld" , x) 26 #define SPACE printf(" ") 27 #define PUT puts("") 28 #define LPUP(i , j , k) for(int i = j ; i <= k ; ++i) 29 #define LPDW(i , j , k) for(int i = j ; i >= k ; --i) 30 #define PB(x) push_back(x) 31 #define ALL(A) A.begin(), A.end() 32 #define SZ(A) int((A).size()) 33 #define LBD(A, x) (lower_bound(ALL(A), x) - A.begin()) 34 #define UBD(A, x) (upper_bound(ALL(A), x) - A.begin()) 35 #define LOCAL 36 static const double PI = acos(-1.0); 37 static const double EPS = 1e-8; 38 static const int INF = 0X3fffffff; 39 typedef long long LL; 40 typedef double DB; 41 template<class T> inline 42 void read(T &x) 43 { 44 x = 0; 45 int f = 1 ; char ch = getchar(); 46 while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -1; ch = getchar();} 47 while (ch >= ‘0‘ && ch <= ‘9‘) {x = x * 10 + ch - ‘0‘; ch = getchar();} 48 x *= f; 49 } 50 51 /************************Little Pea****************************/ 52 static const int MAXN = 80; 53 int n; 54 struct Node 55 { 56 int v; 57 Node* next[27]; 58 Node () 59 { 60 v = 0; 61 CLR(next , NULL); 62 } 63 }; 64 Node* root; 65 bool Insert(char *s , int len) 66 { 67 Node* p = root; 68 bool flag = 1; 69 for(int i = 0 ; i < len ; ++i) 70 { 71 int id = s[i] - ‘a‘; 72 if(p->next[id] == NULL) 73 { 74 p->next[id] = new Node(); 75 flag = 0; 76 } 77 p = p->next[id]; 78 if(p->v) 79 return 0; 80 } 81 if(flag) 82 return 0; 83 ++(p->v); 84 return 1; 85 } 86 int main() 87 { 88 #ifndef ONLINE_JUDGE 89 //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin); 90 #endif 91 read(n); 92 root = new Node(); 93 bool flag = 1; 94 char ans[MAXN] = {‘\0‘}; 95 while(n--) 96 { 97 char data[MAXN] = {‘\0‘}; 98 SFS(data); 99 if(flag)100 {101 if(!Insert(data , strlen(data)))102 {103 flag = 0;104 strcpy(ans , data);105 }106 }107 }108 if(flag)109 puts("GOOD SET");110 else111 {112 puts("BAD SET");113 printf("%s" , ans);114 }115 116 #ifndef ONLINE_JUDGE117 fclose(stdin), fclose(stdout);118 #endif119 }
Test data:
1 Input: 2 100 3 hgiiccfchbeadgebc 4 biiga 5 edchgb 6 ccfdbeajaeid 7 ijgbeecjbj 8 bcfbbacfbfcfbhcbfjafibfhffac 9 ebechbfhfcijcjbcehbgbdgbh 10 ijbfifdbfifaidje 11 acgffegiihcddcdfjhhgadfjb 12 ggbdfdhaffhghbdh 13 dcjaichjejgheiaie 14 d 15 jeedfch 16 ahabicdffbedcbdeceed 17 fehgdfhdiffhegafaaaiijceijdgbb 18 beieebbjdgdhfjhj 19 ehg 20 fdhiibhcbecddgijdb 21 jgcgafgjjbg 22 c 23 fiedahb 24 bhfhjgcdbjdcjjhaebejaecdheh 25 gbfbbhdaecdjaebadcggbhbchfjg 26 jdjejjg 27 dbeedfdjaghbhgdhcedcj 28 decjacchhaciafafdgha 29 a 30 hcfibighgfggefghjh 31 ccgcgjgaghj 32 bfhjgehecgjchcgj 33 bjbhcjcbbhf 34 daheaggjgfdcjehidfaedjfccdafg 35 efejicdecgfieef 36 ciidfbibegfca 37 jfhcdhbagchjdadcfahdii 38 i 39 abjfjgaghbc 40 bddeejeeedjdcfcjcieceieaei 41 cijdgbddbceheaeececeeiebafgi 42 haejgebjfcfgjfifhihdbddbacefd 43 bhhjbhchdiffb 44 jbbdhcbgdefifhafhf 45 ajhdeahcjjfie 46 idjajdjaebfhhaacecb 47 bhiehhcggjai 48 bjjfjhiice 49 aif 50 gbbfjedbhhhjfegeeieig 51 fefdhdaiadefifjhedaieaefc 52 hgaejbhdebaacbgbgfbbcad 53 heghcb 54 eggadagajjgjgaihjdigihfhfbijbh 55 jadeehcciedcbjhdeca 56 ghgbhhjjgghgie 57 ibhihfaeeihdffjgddcj 58 hiedaegjcdai 59 bjcdcafgfjdejgiafdhfed 60 fgdgjaihdjaeefejbbijdbfabeie 61 aeefgiehgjbfgidcedjhfdaaeigj 62 bhbiaeihhdafgaciecb 63 igicjdajjdegbceibgebedghihihh 64 baeeeehcbffd 65 ajfbfhhecgaghgfdadbfbb 66 ahgaccehbgajcdfjihicihhc 67 bbjhih 68 a 69 cdfcdejacaicgibghgddd 70 afeffehfcfiefhcagg 71 ajhebffeh 72 e 73 hhahehjfgcj 74 ageaccdcbbcfidjfc 75 gfcjahbbhcbggadcaebae 76 gi 77 edheggceegiedghhdfgabgcd 78 hejdjjbfacggdccgahiai 79 ffgeiadgjfgecdbaebagij 80 dgaiahge 81 hdbaifh 82 gbhccajcdebcig 83 ejdcbbeiiebjcagfhjfdahbif 84 g 85 ededbjaaigdhb 86 ahhhcibdjhidbgefggdjebfcf 87 bdigjaehfchebiedajcjdh 88 fjehjgbdbaiifi 89 fbgigbdcbcgffdicfcidfdafghajc 90 ccajeeijhhb 91 gaaagfacgiddfahejhbgdfcfbfeedh 92 gdajaigfbjcdegeidgaccjfi 93 fghechfchjbaebcghfcfbdicgaic 94 cfhigaciaehacdjhfcgajgbhhgj 95 edhjdbdjccbfihiaddij 96 cbbhagjbcadegicgifgghai 97 hgdcdhieji 98 fbifgbhdhagch 99 cbgcdjea100 dggjafcajhbbbaja101 bejihed102 eeahhcggaaidifdigcfjbficcfhjj103 OutPut:104 BAD SET105 d
No Prefix Set(Tire Tree)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。