Immediate Decodability

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1335 字

多组 01 串建 Trie 判前缀，遇 9 结算

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1474
// 题意：多组 01 串（每组以单独的 9 结束），判断该组中是否存在一个串是另一个串的前缀，逐组输出结果。
// 思路：对每组数据建 Trie，插入途中命中已有单词结尾（当前串被前缀命中），或插完发现当前结点已有儿子（当前串是别人的前缀），都说明不合法。
// 复杂度：O(所有串总长度) 时间 / O(所有串总长度) 空间
// 易错点：读到 9 时才结算并输出该组，不能在读不到输入后再补输出最后一组。
// 易错点：判定前缀要看「当前结点已有儿子」这个标记，该标记必须在建子结点时顺手打到父结点上。
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int ch[2];
    bool ed;
    bool has;
    Node(){
        ch[0] = ch[1] = 0;
        ed = false;
        has = false;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<Node> tr;
    tr.push_back(Node());
    bool bad = false;
    int t = 1;
    string s;
    while(cin >> s){
        if(s == "9"){
            cout << "Set " << t << " is " << (bad ? "not " : "") << "immediately decodable\n";
            t++;
            tr.clear();
            tr.push_back(Node());
            bad = false;
            continue;
        }
        int u = 0;
        for(int i = 0; i < (int)s.size(); i++){
            int c = s[i] - '0';
            if(!tr[u].ch[c]){
                tr[u].ch[c] = (int)tr.size();
                tr[u].has = true;
                tr.push_back(Node());
            }
            u = tr[u].ch[c];
            if(tr[u].ed) bad = true;
        }
        if(tr[u].has) bad = true;
        tr[u].ed = true;
    }
    return 0;
}

Immediate Decodability

正文

一本通·提高篇的其它内容