Trie Tree POJ 2001   2013-01-17


trie tree poj 2001 shortest prefixes

POJ 2001 Shortest Prefixes

#include <iostream>  
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <map>
#include <set>
#include <iterator>
#include <algorithm>
#include <functional>
#include <utility>
#include <sstream>
#include <climits>
#include <cassert>
#define BUG puts("here!!!");

using namespace std;
const int N = 1010;
const int kind = 26;
char str[N][25];
struct Node {
int num;
bool tail;
Node* next[kind];
Node() : num(1), tail(false) {
memset(next, 0, sizeof(next));
}
};
void insert(Node* root, char *s) {
Node* p = root;
int i = 0, index;
while(s[i]) {
index = s[i] - 'a';
if(p->next[index] == NULL) {
p->next[index] = new Node();
}
else p->next[index]->num++;
p = p->next[index];
i++;
}
p->tail = true;
}
void solve(Node* root, int count) {
for(int i = 0; i < count; i++) {
Node* p = root;
int len = strlen(str[i]);
char* s = str[i];
cout << s << ' ';
for(int j = 0; j < len; j++) {
cout << s[j];
int index = s[j] - 'a';
if(p->next[index]->num == 1) {
break;
}
p = p->next[index];
}
cout << endl;
}
}
int main() {
Node* root = new Node(); // 根节点不包含任何字符
int i = 0, count = 0;
while(scanf("%s", str[i]) == 1) {
insert(root, str[i]);
i++;
}
count = i;
solve(root, count);
return 0;
}

分享到:


  如果您觉得这篇文章对您的学习很有帮助, 请您也分享它, 让它能再次帮助到更多的需要学习的人. 您的支持将鼓励我继续创作 !
本文基于署名4.0国际许可协议发布,转载请保留本文署名和文章链接。 如您有任何授权方面的协商,请邮件联系我。

Contents

  1. POJ 2001 Shortest Prefixes