BOJ 9250 문자열 집합 판별

 

문제 링크 : https://www.acmicpc.net/problem/9250

9250번: 문자열 집합 판별

 

여러 키워드를 동시에 검색하는 아호-코라식(Aho-Corasick) 알고리즘 연습 문제이다.

 

문서 전체의 내용을 하나의 스트링으로 간주하고 여러개의 키워드의 존재 여부나 등장 횟수를 찾는 상황을 생각해보자.

각 지점에서  키워드와 일치하는지 비교하는 무식한 방법이 있을 것이다.

하지만 키워드의 개수가 늘어나고 각 키워드의 길이가 짧지 않다면...

 

효율적인 알고리즘 대부분이 그러하듯이 앞선 작업을 가능한 많이 재사용하고자 한다.

한 키워드의 접미사이면서 다른 키워드의 접두사인 것들을 미리 조사해두면 검색의 효율을 높일 수 있는데.

'weeeb' 과 'eeebay' 두 키워드를 가지고 생각해보자.

 

두 키워드는 eeeb 를 공통으로 포함하고 있다.

weeeb 을 문자열과 비교하는 과정에서 이미 eeebay의 앞부분 네 글자가 일치함을 알고 있다는 뜻이다.

w 위치부터 다시 검색하지 않고 일치한 가장 긴 접두사 위치로 가서 계속 검색을 하면 될 것이다.

 

다음 코드에서 prv 변수가 다음 검색 위치를 제시해 준다.

즉 trie 가 문자열을 소모할 때 다음 문자가 일치하지 않을 경우 어디에서 검색을 이어갈 것인지를 알려 준다.

 

#include<bits/stdc++.h>

using namespace std;

char str[10001];

struct trie {
    char c; bool isEnd;
    trie *prv, *children[26];

    trie(): isEnd{false} {
        for(int i=0;i<26;i++) children[i]=nullptr;
    }
    ~trie() {
        for(int i=0;i<26;i++) if(children[i]!=nullptr)
            delete children[i];
    }

    void add(char *p){
        if(*p==0) { isEnd=true; return; }

        int nxt=*p-'a';
        if(children[nxt]==nullptr) 
            children[nxt]= new trie();
        children[nxt]->add(p+1);
    }
} *rt; 

int main(){
    //freopen("data.txt","r",stdin);
    int n; scanf("%d",&n);
    rt=new trie();
    for(int i=0;i<n;i++){
        scanf("%s", str);
        rt->add(str);
    }

    rt->prv=rt;
    queue<trie*> q;
    q.push(rt);
    while(!q.empty()){
        trie *cur=q.front();
        q.pop();

        for(int i=0;i<26;i++){
            trie *nxt=cur->children[i];
            if(nxt==nullptr) continue;

            if(cur==rt) nxt->prv=rt;
            else {
                trie *t=cur->prv;
                while(t!=rt && t->children[i]==nullptr)
                    t=t->prv;
                if(t->children[i]) 
                    t=t->children[i];
                nxt->prv=t;
            }

            if(nxt->prv->isEnd) nxt->isEnd=true;
            q.push(nxt);
        }
    }

    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%s",str);

        trie *cur=rt;
        bool b=false;
        for(int j=0;str[j]!=0;j++){
            int id=str[j]-'a';
            while(cur!=rt && cur->children[id]==nullptr)
                cur=cur->prv;
            if(cur->children[id])
                cur=cur->children[id];
            if(cur->isEnd){
                b=true;
                break;
            }
        }
        if(b) printf("YES\n");
        else printf("NO\n");
    }
}

 

queue 는 직관적으로 자연스럽다.

예를 들어 n 문자가 일치한 후에 불일치가 일어났다면 찾아야 할 것은 n 문자 이하의 접두사일 것이다.

따라서 queue 를 사용해서 각 키워드의 접두사들을 동시에 길이별로 처리해 나간 것이라 생각하면 이해하지 쉽다.