icontofig | 发布于 2019-04-06 15:14:55 | 阅读量 281 | 字符串 Trie
发布于 2019-04-06 15:14:55 | 字符串 Trie

 题解

本题为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;
}

 


内容更新于: 2019-04-06 15:14:55
链接地址: http://blog.leanote.com/post/icontofig/Trie%E6%A0%91%E6%A8%A1%E6%9D%BF

上一篇: BZOJ 2561 最小生成树(最小割模型)

下一篇: POJ3461Oulipo -KMP模板题

281 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航