글 읽기 - 아호코라식으로 풀었습니다. 런타임에러가 뜨네요....

cgc96 4년 전 0

이유가 뭘까요..

makemarker함수로 패턴을 입력받으면 돌연변이들을 만들어주고 아호코라식을 사용해서 해답을 구하는 코드입니다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <queue>
#include <string.h>

using namespace std;

int N, M, cnt;
string s, pattern, marker[1000005];

struct Trie{

    Trie *go[26]; //현재 코드에서 해당 문자를 받으면 가는 노드
    Trie *fail; //현재 노드에서 해당 문자의 go 목적지가 없을때 가는 노드
    bool output; //현재 노드에 도달하면 찾는 문자열 집합

    Trie(){
        fill(go, go+26, nullptr);
        output = false;
    }
    ~Trie(){
        for(int i = 0; i < 26; i++)
            if(go[i]) delete go[i];
    }
    void Insert(const char* key){

        if(*key == '\0'){
            output = true;
            return;
        }
        int next = *key - 'A';
        if(!go[next]){
            go[next] = new Trie;
        }
        go[next]->Insert(key+1);
    }
};

void makemarker(){
    int plen = pattern.length();
    int len = 1;
    while(1){
        string temp = pattern;
        reverse(temp.begin(), temp.begin()+len);
        marker[cnt] = temp;
        len++; cnt++;
        if(len == plen+1){
            len = 1;
            while(1){
                temp = pattern;
                reverse(temp.begin()+len, temp.begin()+plen);
                marker[cnt] = temp;
                len++; cnt++;
                if(len == plen-1) break;
            }
            break;
        }
    }
}

int main()
{
    //freopen("input.text","r",stdin);

    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &N, &M);
        cin >> s >> pattern;

        makemarker();
        Trie* root = new Trie;
        int plen = pattern.length();

        for(int i = 0; i < cnt; i++){
            char ch[1000005];
            strcpy(ch, marker[i].c_str());
            //cout << ch <<endl;
            root->Insert(ch);
        }
        queue<Trie*> Q;
        root->fail = root;
        Q.push(root);
        while(!Q.empty()){
            Trie *current = Q.front();
            Q.pop();

            for(int i = 0; i < 26; i++){
                Trie *next = current->go[i];
                if(!next) continue;

                if(current == root) next->fail = root;
                else{
                    Trie *dest = current->fail;
                    while(dest != root && !dest->go[i])
                        dest = dest->fail;
                    if(dest->go[i]) dest = dest->go[i];
                    next->fail = dest;
                }
                if(next->fail->output) next->output = true;
                Q.push(next);
            }
        }

        Trie* current = root;
        int result = 0;
        for(int c = 0; s[c]; c++){
            int next = s[c]-'A';

            while(current != root && !current->go[next])
                current = current->fail;
            if(current->go[next])
                current = current->go[next];
            if(current->output){
                result++;
            }
        }

        printf("%d\n", result);
        delete root;
        for(int i = 0; i < 1000005; i++){
            marker[i] = "";
        }
        cnt = 0;
    }
}

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

문제

문제

출처

ICPC

아호코라식으로 풀었습니다. 런타임에러가 뜨네요....

cgc96 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말