題意：
? ? ? 給你一堆電話號(hào)，問(wèn)你這些電話號(hào)后面有沒(méi)有相互沖突的，沖突的條件是當(dāng)前這個(gè)電話號(hào)是另一個(gè)電話號(hào)的前綴，比如有 123456789 123,那么這兩個(gè)電話號(hào)就沖突了，直接輸出NO。

思路： ?

? ? ? 說(shuō)白了就是前綴匹配，也就是以當(dāng)前字符串為前綴的字符串有幾個(gè)，只要有一個(gè)或者更多那么就直接NO了，快速的判斷前綴的問(wèn)題我們可以直接字典樹記錄前綴，先把所有的字符串都存在字典里，然后在枚舉每一個(gè)，只要有一個(gè)是前綴（不算自己）那么就直接NO了，這里要注意一點(diǎn)，每次都要把Tree的內(nèi)存清空，不然不同的mallco不釋放，測(cè)試數(shù)據(jù)多了就MLE了。

#include<stdio.h> #include<string.h> #include<stdlib.h> char str[10005][12];typedef struct Tree {Tree *next[10];int v; }Tree;Tree root;void Buid_Tree(char *str) {int len = strlen(str);Tree *p = &root ,*q;for(int i = 0 ;i < len ;i ++){int id = str[i] - '0';if(p -> next[id] == NULL){q = (Tree *) malloc(sizeof(root));q -> v = 1;for(int j = 0 ;j < 10 ;j ++)q -> next[j] = NULL;p -> next[id] = q;p = p -> next[id];}else{p = p -> next[id];p -> v ++;}} }int Find(char *str) {int len = strlen(str);Tree *p = &root;for(int i = 0 ;i < len ;i ++){int id = str[i] - '0';p = p -> next[id];if(p == NULL) return 0;}return p -> v; }bool solve(int n) {for(int i = 1 ;i <= n ;i ++)if(Find(str[i]) != 1) return 0;return 1; }int dealTree(Tree* T) {int i;if(T==NULL)return 0;for(i=0;i<10;i++){if(T->next[i]!=NULL)dealTree(T->next[i]);}free(T);return 0; }int main () {int t ,n ,i;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);for(i = 0 ;i < 10 ;i ++)root.next[i] = NULL;for(i = 1 ;i <= n ;i ++){scanf("%s" ,str[i]);Buid_Tree(str[i]);}if(solve(n)) puts("YES");else puts("NO");dealTree(&root);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu1671 字典树记录前缀出现次数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。