poj - IMMEDIATE DECODABILITY Trie树模板

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 题解

本题为Trie(字典树)的模板题。

我们先来说一下Trie的基本构造:

Trie树,又名字典树,故名思义,将字符串各个字符以类似字典的方式构造成一棵树,以便检索。

Trie树的每一个节点的深度代表着当前检索到的字符串的长度。而Trie树的每两个节点之间的边可以认为是代表着字典中的一个字符。

字典树的根节点是我们检索字符串的起始,我们每次检索字符串都是由这个根节点开始的。我们每检索一个字符,就顺延着当前这个字符所代表的边走向下一个节点。

有些节点会打一个flag标记,这代表着Trie树中一个单词的结束。

以上是Trie树的基本构造。

对于这个题目,它的要求是判断任意一个字符串不能是另外任意一个字符串的前缀。

所以我们对每个节点加一个cnt标记统计在建立Trie树过程中当前节点的访问次数。

所以题意在我们的思路中,就变为了:

在建Trie树的过程中,如果当前访问的节点打上了flag标记(一个单词的结尾)并且访问次数大于了1,则说明出现一个单词为其它单词的前缀。就输出not immediately decodable,如果建完Trie都不存在这样的单词,就输出immediately decodable。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s;
int num = 0;
const int maxn = 10005;
struct trie{
    int cnt;
    bool flag;
    int child[2];
}pool[maxn],root;
bool pp = false;
void init(){
    memset(pool,0,sizeof(pool));
    num = 0;
    root = pool[0];
    pp = false;
    return;
}
int sum = 0;
int main(){
    init();
    while(cin >> s){
        int len = s.size();
        if(s[0] == '9'){
            sum++;
            if(!pp)cout << "Set " << sum << " is immediately decodable" << endl;
            else cout << "Set " << sum << " is not immediately decodable" << endl;
            init();
            continue;
        }
        root.cnt++;
        trie *now = &root;
        for(int i = 0;i < len;++i){
            int p = (int)(s[i] - '0');
            if(now->child[p] == 0){
                now->child[p] = ++num;
            }
            now = &pool[now->child[p]];
            now->cnt++;
            if(now->flag && now->cnt > 1){
                pp = true;
            }
            if(i == len-1){
                now->flag = true;
            }
        }
    }
    return 0;
}

 

Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00