library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub shibh308/library

:heavy_check_mark: verify/suffixtree.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"

#include <bits/stdc++.h>

using namespace std;


#include "../lib/classes/avl_map.cpp"
#include "../lib/classes/suffixtree.cpp"


signed main(){
    string s, t;
    cin >> s >> t;
    SuffixTree st(s);
    vector<int> res;
    res.reserve(s.size());
    stack<int> sta;
    int node = st.match(t).first;
    sta.push(node);
    while(!sta.empty()){
        int x = sta.top();
        sta.pop();
        if(x == st.n)
            continue;
        if(x < st.n)
            res.emplace_back(x);
        for(auto p : st.avl.list(st.nodes[x].child)){
            sta.push(p.second);
        }
    }
    sort(res.begin(), res.end());
    for(auto x : res)
        printf("%d\n", x);
}
#line 1 "verify/suffixtree.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"

#include <bits/stdc++.h>

using namespace std;


#line 1 "lib/classes/avl_map.cpp"
template <typename T, typename U>
struct AVL_map{
    struct Node{
        int height;
        T key;
        U val;
        Node(T key, U val) : key(key), val(val), height(1){c[0] = 0; c[1] = 0;}
        int c[2];
    };
    vector<Node> nodes;
    stack<int> st;
    AVL_map(){
        nodes.emplace_back(T(), U());
        nodes[0].height = 0;
    }
    template <bool inv>
    int balance_factor(int x){return (nodes[nodes[x].c[0]].height - nodes[nodes[x].c[1]].height) * (inv ? -1 : 1);}
    void _update(int x){
        if(x == 0)
            return;
        nodes[x].height = max(nodes[nodes[x].c[0]].height, nodes[nodes[x].c[1]].height) + 1;
    }
    template <bool is_right>
    int rotate(int x){
        int y = nodes[x].c[1 ^ is_right];
        nodes[x].c[1 ^ is_right] = nodes[y].c[0 ^ is_right];
        nodes[y].c[0 ^ is_right] = x;
        _update(x);
        _update(y);
        return y;
    }
    template <bool inv>
    int _balance(int x){
        if(balance_factor<inv>(x) == 2){
            if(balance_factor<inv>(nodes[x].c[0 ^ inv]) < 0)
                nodes[x].c[0 ^ inv] = rotate<inv>(nodes[x].c[0 ^ inv]);
            x = rotate<1 ^ inv>(x);
        }
        return x;
    }
    int balance(int x){
        x = _balance<false>(x);
        x = _balance<true>(x);
        _update(x);
        return x;
    }
    int add(int x, T key, U val){
        if(x == 0){
            if(st.empty()){
                nodes.emplace_back(key, val);
                return nodes.size() - 1;
            }
            else{
                int y = st.top();
                st.pop();
                nodes[y] = Node(key, val);
                return y;
            }
        }
        else if(key == nodes[x].key)
            nodes[x].val = val;
        else if(key < nodes[x].key)
            nodes[x].c[0] = add(nodes[x].c[0], key, val);
        else
            nodes[x].c[1] = add(nodes[x].c[1], key, val);
        x = balance(x);
        return x;
    }
    // 子が片方しかない時にノードを削除する
    int _erase_top(int x, bool del){
        for(int i = 0; i < 2; ++i){
            if(nodes[x].c[i] == 0){
                int y = nodes[x].c[i ^ 1];
                if(del)
                    st.push(x);
                return y;
            }
        }
		return -1;
    }
    // 最小の要素をdstにコピーしてから削除する
    int _copy_erase(int x, int dst, bool del){
        if(nodes[x].c[0] == 0){
            nodes[dst].val = nodes[x].val;
            return _erase_top(x, del);
        }
        nodes[x].c[0] = _copy_erase(nodes[x].c[0], dst, del);
        x = balance(x);
        return x;
    }
    int erase(int x, T key, bool del = true){
        if(key < nodes[x].key)
            nodes[x].c[0] = erase(nodes[x].c[0], key, del);
        else if(nodes[x].key < key)
            nodes[x].c[1] = erase(nodes[x].c[1], key, del);
        else{
            if(nodes[x].c[0] == 0 || nodes[x].c[1] == 0)
                return _erase_top(x, del);
            nodes[x].c[1] = _copy_erase(nodes[x].c[1], x, del);
        }
        x = balance(x);
        return x;
    }
    pair<U, bool> get(int x, T key){
        if(x == 0)
            return {U(), false};
        else if(key == nodes[x].key)
            return {nodes[x].val, true};
        else if(key < nodes[x].key)
            return get(nodes[x].c[0], key);
        else
            return get(nodes[x].c[1], key);
    }
    vector<pair<T, U>> list(int x){
        vector<pair<T, U>> v;
        stack<pair<int,bool>> sta;
        sta.emplace(x, false);
        bool add;
        while(!sta.empty()){
            tie(x, add) = sta.top();
            sta.pop();
            if(x == 0)
                continue;
            if(add)
                v.emplace_back(nodes[x].key, nodes[x].val);
            else{
                if(nodes[x].c[1])
                    sta.emplace(nodes[x].c[1], false);
                sta.emplace(x, true);
                if(nodes[x].c[0])
                    sta.emplace(nodes[x].c[0], false);
            }
        }
        return v;
    }
};
#line 1 "lib/classes/suffixtree.cpp"
struct SuffixTree{
    // Weinerでの構築 [0,n)が葉 nが根 [n+1,)が内部節点 番兵'$'
    struct Node{
        int pos = -1, par = -1, par_len = -1, dep = 0, slink = -1;
        int child = 0, plink = 0;
    };
    AVL_map<char,int> avl;
    int n;
    string s;
    vector<Node> nodes;
    vector<int> sa, sa_inv, lcp;
    SuffixTree(string& _s) : n(_s.size() + 1), s(_s + "$"), nodes(_s.size() + 3), sa(n), sa_inv(n), lcp(n){
        nodes[n].slink = n;
        nodes[n].par = n + 1;
        nodes[n].par_len = 1;
        for(int i = n - 1; i >= 0; --i)
            add(i);
        make_sa();
    }
    void make_sa(){
        stack<pair<int,bool>> sta;
        int cnt = 0;
        int lca = 0;
        sta.emplace(n, false);
        int x;
        bool is_lca;
        while(!sta.empty()){
            tie(x, is_lca) = sta.top();
            sta.pop();
            if(is_lca){
                lca = min(lca, x);
                continue;
            }
            if(x < n){
                sa[cnt] = x;
                if(cnt > 0)
                    lcp[cnt - 1] = lca;
                lca = nodes[x].dep;
                sa_inv[x] = cnt++;
            }
            auto chi = avl.list(nodes[x].child);
            for(int i = chi.size() - 1; i >= 0; --i){
                sta.emplace(nodes[x].dep, true);
                sta.emplace(chi[i].second, false);
            }
        }
    }
    int child(int x, char c){
        auto res = avl.get(nodes[x].child, c);
        if(res.second)
            return res.first;
        else
            return -1;
    }
    int plink(int x, char c){
        if(x == n + 1)
            return n;
        auto res = avl.get(nodes[x].plink, c);
        if(res.second)
            return res.first;
        else
            return -1;
    }
    void attach(int par, int ch, char c, int len){
        nodes[par].child = avl.add(nodes[par].child, c, ch);
        nodes[ch].par_len = len;
        nodes[ch].par = par;
        nodes[ch].dep = nodes[par].dep + len;
    }
    void add(int i){
        int old = i + 1;
        vector<int> path(1, old);
        int vlen = s.size() - i;
        while(plink(old, s[i]) == -1){
            vlen -= nodes[old].par_len;
            old = nodes[old].par;
            path.emplace_back(old);
        }
        int now = plink(old, s[i]);
        int ch = child(now, s[i + nodes[now].dep]);
        int old_idx = path.size() - 1;
        if(ch != -1){
            int idx = nodes.size();
            nodes.emplace_back();
            int pos;
            for(pos = nodes[ch].pos - nodes[ch].par_len; s[pos] == s[i + vlen]; pos += nodes[old].par_len){
                old = path[--old_idx];
                vlen += nodes[old].par_len;
            }
            nodes[idx].pos = pos;
            attach(now, idx, s[nodes[ch].pos - nodes[ch].par_len], nodes[ch].par_len - (nodes[ch].pos - pos));
            attach(idx, ch, s[pos], nodes[ch].pos - pos);
            now = idx;
            nodes[old].plink = avl.add(nodes[old].plink, s[i], idx);
            nodes[idx].slink = old;
        }
        old = path.front();
        nodes[old].plink = avl.add(nodes[old].plink, s[i], i);
        nodes[i].slink = old;
        attach(now, i, s[i + nodes[now].dep], s.size() - (i + nodes[now].dep));
        nodes[i].pos = n;
    }
    void print(int st = -1, string t = ""){
        if(st == -1)
            st = n;
        if(st < n){
            cout << st << ": " << t << endl;
        }
        else{
            cout << "-" << ": " << t << endl;
        }
        for(auto p : avl.list(nodes[st].child)){
            int ch = p.second;
            t += s.substr(nodes[ch].pos - nodes[ch].par_len, nodes[ch].par_len);
            print(ch, t);
            t.erase(prev(t.end(), nodes[ch].par_len), t.end());
        }
    }
    // 途中でマッチした場合は (マッチした辺の子, 子側からの距離) を返す
    // ノードでマッチした場合は (マッチしたノード, 0) になる
    // マッチしなかったら (n, 0) を返す
    pair<int,int> match(string t){
        int i = 0;
        int x = n;
        auto res = avl.list(nodes[x].child);

        while(i != t.size()){
            int ch = child(x, t[i]);
            if(ch == -1)
                return {-1, -1};
            for(int j = 0; j < nodes[ch].par_len; ++i, ++j){
                if(i == t.size()){
                    return {ch, nodes[ch].par_len - j};
                }
                int k = nodes[ch].pos - nodes[ch].par_len + j;
                if(s[k] != t[i])
                    return {n, -1};
            }
            x = ch;
        }
        return {x, 0};
    }
};
#line 10 "verify/suffixtree.test.cpp"


signed main(){
    string s, t;
    cin >> s >> t;
    SuffixTree st(s);
    vector<int> res;
    res.reserve(s.size());
    stack<int> sta;
    int node = st.match(t).first;
    sta.push(node);
    while(!sta.empty()){
        int x = sta.top();
        sta.pop();
        if(x == st.n)
            continue;
        if(x < st.n)
            res.emplace_back(x);
        for(auto p : st.avl.list(st.nodes[x].child)){
            sta.push(p.second);
        }
    }
    sort(res.begin(), res.end());
    for(auto x : res)
        printf("%d\n", x);
}
Back to top page