글 읽기 - bitmask & vector 아호코라식 시간 초과 질문

nuclear852 3년 전 0

다른 분의 코드를 참고해서 bitmask와 vector<Trie*>를 이용한 아호코라식을 구현하였습니다.

이후 terminal node에 maximum 길이를 지정해둔 후

terminal node에 방문할 때마다 방문한 인덱스를 i라 할때

{i- len(term_node) + 1, i} 를 lazy_propagation segment tree를 이용하여 string의 해당 인덱스들을 1로 저장한 후

마지막에 1의 갯수를 세서 정답을 구하는 방법입니다.

근데 자꾸 시간 초과가 나서, 3일 넘게 다르게 시도해보다가 어느 부분이 잘못됐는지 모르겠어서 질문드립니다.

조언주시면 감사드리겠습니다..

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;


int N, M;
string A, B;
char tmp[300050];
int tree[1212121];
int lazy[1212121];

void update(int index, int start, int end, int left, int right) {
    if(lazy[index]) {
        tree[index] = (end - start + 1);
        if(start != end) {
            lazy[index * 2] = 1;
            lazy[index * 2 + 1] = 1;
        }
        lazy[index] = 0;
    }

    if(right < start || left > end) return;
    if(left <= start && end <= right) {
        tree[index] = (end - start + 1);
        if(start != end) {
            lazy[index * 2] = 1;
            lazy[index * 2 + 1] = 1;
        }
        return;
    }
    
    int mid = (start + end) / 2;
    update(index * 2, start, mid, left, right);
    update(index * 2 + 1, mid + 1, end, left, right);
    tree[index] = tree[index * 2] + tree[index *2 + 1];
}

int find(int index, int start, int end, int left, int right) {
    if(lazy[index]) {
        tree[index] = (end - start + 1);
        if(start != end) {
            lazy[index * 2] = 1;
            lazy[index * 2 + 1] = 1;
        }
        lazy[index] = 0;
    }
    if(right < start || left > end) return 0;
    if(left <= start && end <= right) {
        return tree[index];
    }
    if(start == end) return 0;
    int mid = (start + end) / 2;
    return find(index*2, start, mid, left, right) + find(index*2+1, mid+1, end, left, right);

}

int to_num(char ch) {
    return ch - 'a';
}

bool isExist(int exist, int ch) {
    return exist & (1 << ch);
}

int whatPathofN(int exist, int n) {
    int path = -1;
    for(int i=0; i<n; i++) {
        exist -= exist & (-exist);
    }
    for(int i=0; i<26; i++) {
        int tmp_exist = (exist & (-exist)) >> i;
        if(tmp_exist & 1) {
            path = i;
            break;
        }
    }
    return path;
}

int position(int exist, int ch) {
    int cnt = 0;
    for(int i=0; i<ch; i++) {
        cnt += isExist(exist, i);
    }
    return cnt;
}

class Trie{
    public: 
        vector<Trie*> go;
        Trie* fail;
        int isTerm;
        int exist;
    
        Trie() {
            fail = nullptr;
            isTerm = 0;
            exist = 0;
        }

        ~Trie() {
            for(auto trie: go) {
                delete trie;
            }
        }

        void insert(string str, int idx) {
            if(idx == str.size()) {
                isTerm = str.size();
                return;
            }
            int path = to_num(str[idx]);
            int pos = position(exist, path);
            if(!isExist(exist, path)) {
                exist |= (1 << path);
                go.insert(go.begin() + pos, new Trie());
            }
            go[pos]->insert(str, idx+1);
            return;
        }
};

class AhoCorasick {
    public:
        Trie* root;
        AhoCorasick() {
            root = new Trie();
        }
        ~AhoCorasick() {
            delete root;
        }
        void insert(string str) {
            root->insert(str, 0);
            return;
        }
        void make_failFunc() {
            queue<Trie*> q; q.push(root);
            while(!q.empty()) {
                Trie* cur = q.front(); q.pop();
                for(int i=0; i<cur->go.size(); i++) {
                    Trie* next = cur->go[i];
                    
                    if(cur == root) {
                        next->fail = root;
                    }
                    else {
                        int path = whatPathofN(cur->exist, i);
                        Trie* f = cur->fail;
                        while(f != root && !isExist(f->exist, path)) {
                            f = f->fail;
                        }
                        if(isExist(f->exist, path)) f = f->go[position(f->exist, path)];
                        next->fail = f;
                    }
                    if(next->fail->isTerm) next->isTerm = max(next->isTerm, next->fail->isTerm);
                    q.push(next);
                }
            }
        }
        vector<pair<int, int> > solve(string str) {
            vector<pair<int, int> > v;
            Trie *cur = root;
            for(int i = 0; i < str.size(); i++) {
                int path = to_num(str[i]);
                while(cur != root && !isExist(cur->exist, path)) {
                    cur = cur->fail;
                }
                if(isExist(cur->exist, path)) cur = cur->go[position(cur->exist, path)];
                if(cur->isTerm) {
                    v.push_back({i-cur->isTerm+1, i});
                }
            }
            return v;
        }
};

AhoCorasick* ac = new AhoCorasick();
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> N;
    cin >> A;
    cin >> M;

    while(M--) {
        cin >> B;
        if(B.size() <= A.size()) ac->root->insert(B, 0);
    }
    ac->make_failFunc();
    auto v = ac->solve(A);
    for(auto val: v) {
        update(1, 0, A.size()-1, val.first, val.second);
    }
    
    printf("%d", A.size()- find(1, 0, A.size()-1, 0, A.size()-1));
    delete ac;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

bitmask & vector 아호코라식 시간 초과 질문

nuclear852 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말