題意很好理解就不說了,然後這道題其實不用字典樹更簡單,但是為了練習trie樹就寫了一下,1A了哈哈,再對比了一下討論區的大神代碼,發現我還是寫復雜了。。。
思路:
想到利用字典樹,繼承字典樹原有機制,從底端葉子向上找,每條路徑最先找
到的分叉點再往下(從葉子找上來的這條路)一個字符即為所求(特殊情況,
如果節點處單詞已結束,那麼就輸出整個單詞好了),也就是從上往下找到的
第一個不是路徑重合(has_same_path = true)的情況或者是is_word =
true的情況,用遍歷二叉樹的方法遍歷整個樹得到所有前綴。
判斷has_same_path的情況很簡單,如果當前tmp->next[num]不為空,則
一定has_same_path
,至於pos則是為了讓答案按順序輸出用的
代碼:
/* poj 2001 11152K 16MS */ #include#include #include #include #define MAXN 1005 using namespace std; struct node { node *next[26]; bool has_same_path; bool is_word; int pos; node() { memset(next , 0 , sizeof(next)); has_same_path = is_word = false; pos = -1; } }trie[100005]; int trie_num; struct out { char s[21]; int pos; out() { memset(s , 0 , sizeof(s)); pos = -1; } }ans[MAXN]; int n = 1,id; char str[MAXN][21],tmp_str[21]; bool cmp(out a , out b) { return a.pos < b.pos; } void insert(char *s , int pos)//插入單詞 { int len = strlen(s); node *now = &trie[0]; for(int i = 0;i < len;i ++) { int num = s[i] - 'a'; if(!now->next[num]) now->next[num] = &trie[++trie_num]; else now->next[num]->has_same_path = true; now = now->next[num]; if(now->pos == -1) now->pos = pos; } now->is_word = true; now->pos = pos; } void cons(node *now , int k)//構造答案 { if(!now->has_same_path || now->is_word) { tmp_str[k] = 0; memcpy(ans[++id].s , tmp_str , k); ans[id].pos = now->pos; now->is_word = false;//防止回溯時再次計入 if(!now->has_same_path) return ; } for(int i = 0;i < 26;i ++) { if(now->next[i]) { tmp_str[k] = i + 'a'; cons(now->next[i] , k + 1); } } } int main() { while(scanf("%s" , str[n]) != EOF) { insert(str[n] , n); n ++; } n --; trie[0].has_same_path = true; cons(&trie[0] , 0); sort(ans + 1 , ans + n + 1 , cmp); for(int i = 1;i <= n;i ++) printf("%s %s\n",str[i] , ans[i].s); return 0; }