글 읽기 - 메모리 초과 해결 접근방법에 대해 질문하겠습니다.

cbs0615 6년 전 0

처음에는 한 노드당 26개의 childs 배열을 가지는 형태로 클래스를 작성했는데

메모리 초과가 떳습니다.

그리고 어떻게 하드코딩으로 실제 있는 값만 childs에 추가하고 몇번째 알파벳이 연결되어

있는지를 나타내는 비트맵 exist를 써서 (i번째 값이 1이면 'a'+i가 연결되어있다) 다시 짜봤는데

역시 메모리 초과가 떳습니다.

혹시 힌트라도 주실 분 계신가요

알고리즘을 처음 배워가는 사람입니다.

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int counter = 0;
bool isExist(int bitmap, int pos){
    return (bitmap & (1 << pos))?(true):(false);
}

int toggleOn(int bitmap, int pos){
    return bitmap | (1 << pos);
}

int nth(int bitmap, int alpha){
    int sum = 0;

    while(alpha-- > -1){
        sum += bitmap & 1;
        bitmap = bitmap >> 1;
    }
    return sum;
}

int chr(int bitmap, int j){

    for(int i = 0;i < 26;i ++){
        if((bitmap >> i)&1){
            j--;
            if(j == -1) return i;
        }
    }
    return -1;
}

class trie{
public:
    vector<trie*> childs;
    trie* fail;
    trie* olink;
    int terminal;
    int exist;

    trie(){
        terminal = -1;
        fail = nullptr;
        olink = nullptr;
        exist = 0;
    }

    ~trie(){
        for(int i = 0;i < childs.size();i ++){
            if(childs[i])
                delete(childs[i]);
        }
    }


    void insert(const char* str){
        if(*str == '\0'){
            olink = this;
            terminal = counter ++;
            return;
        }

        trie* there = nullptr;
        if(isExist(exist, *str - 'a')){
            there = childs[nth(exist, *str - 'a')-1];
        }
        else{
            there = new trie();
            childs.insert(childs.begin() + nth(exist, *str - 'a'), 1, there);
            exist = toggleOn(exist, *str-'a');
        }

        there->insert(str+1);
    }
};
int main(void){
    trie* root = new trie();
    string H;
    int N;
    cin >> N >> H;

    int K;
    cin >> K;
    vector<int> ks(K);
    string needle;

    for(int i = 0;i < K;i ++){
        cin >> needle;
        ks[i] = needle.length();
        root->insert(needle.c_str());
    }

    queue<trie*> q;
    q.push(root);
    root->fail = root;

    while(q.size()){
        int qsize = q.size();
        for(int i = 0;i < qsize;i ++){
            trie* here = q.front(); q.pop();

            for(int j = 0;j < here->childs.size();j ++){
                trie* there = here->childs[j];
                int wchr = chr(here->exist, j);

                if(there){
                    if(here == root){
                        there->fail = root;
                    }
                    else{
                        trie* pf = here->fail;
                        while(pf != root && !isExist(pf->exist, wchr)) pf = pf->fail;

                        if(isExist(pf->exist, wchr)) pf = pf->childs[nth(pf->exist, wchr)-1];
                        there->fail = pf;
                    }
                    if(there->fail->olink) there->olink = there->fail->olink;
                    q.push(there);
                }
            }
        }
    }

    trie* tr = root;
    vector<bool> canCovered(N, false);

    for(int i = 0;i < N;i ++){
        while(tr->fail != tr && !isExist(tr->exist, H[i]-'a')) tr = tr->fail;

        if(isExist(tr->exist, H[i]-'a')){
            tr = tr->childs[nth(tr->exist, H[i]-'a')-1];

            trie* tvl = tr->olink;
            if(tvl){
                while(tvl != tvl->olink){
                    tvl = tvl->olink;
                }

                int from = i - ks[tvl->terminal] + 1;
                int to = i+1;
                fill(canCovered.begin() + from, canCovered.begin() + to, true);
            }
        }
    }

    int num = 0;
    for(int i = 0;i < N;i ++){
        if(!canCovered[i]) num++;
    }

    cout << num << endl;

    delete root;

    return 0;
}

cokcjswo 6년 전 0

제 생각에 아호코라식은 문제 원문의 메모리 제한인 512메가 에서만 풀리는 방법인것같습니다 ㅠㅠ

cbs0615 6년 전 0

아 그렇습니까..

후.. 새로운 방법이 있나보군요..

다른 방법을 생각해봐야겠습니다.

감사합니다

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

문제

문제

출처

ICPC

메모리 초과 해결 접근방법에 대해 질문하겠습니다.

cbs0615 6년 전 0

cokcjswo 6년 전 0

cbs0615 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말