BOJ 5735 Emoticons :-)

 

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

5735번: Emoticons :-)

 

아호-코라식(Aho-Corasick) 알고리즘 자체에 대해선 설명을 생략한다.

 

공백으로 대체해야할 문자의 개수를 최소화하는 방법은 무엇일까?

결론부터 말하면 텍스트를 검색해가면서 찾은 키워드(이모티콘)의 마지막 문자를 제거하면 된다.

 

텍스트 중에 등장하는 

               (-:-( 

을 보자. 가운데에 위치한 : 를 제거하면 (-: 과 :-( 의 두 개의 키워드를 제거할 수 있음을 알 수 있다.

만약 첫 문자나 두 번째 문자를 제거하면 첫 키워드는 제거할 수 있지만 두 번째 키워드는 제거되지 않는다.

 

이와 같은 상황은 일반적이다.

최소의 문자를 제거하는 최적해를 상상한다. 

제거한 문자의 위치가 앞에서부터 차례로 키워드가 발견되었을 때 키워드의 마지막 문자가 아닌 경우가 있다면,

그것들 중 최초의 것을 생각한다.

그 문자를 살려두고 키워드 마지막 문자를 지워서 손해보는 경우는 없음을 금새 알 수 있다.

 

#include<bits/stdc++.h>

using namespace std;

struct trie{
    trie *prv, *children[100];
    bool isEnd;
    trie() : isEnd{false}, prv{nullptr} { 
        for(int i=0;i<100;i++) children[i]=nullptr;
    }
    ~trie(){ 
        for(int i=0;i<100;i++ ) if(children[i]) 
            delete children[i]; 
    }
    
    void add(char *p){
        if(*p==0) { isEnd=true; return; }
        int id=*p-32;
        if(!children[id])
            children[id]=new trie();
        children[id]->add(p+1);
    }
} *rt;

int main(){
    while(true){
        int n,m; scanf("%d%d",&n,&m);
        if(n==0) break;
        
        rt=new trie();
        while(n--){
            char str[101];
            scanf("%s", str);
            rt->add(str);
        }

        queue<trie*> q;
        q.push(rt);
        while(!q.empty()){
            trie* cur = q.front();
            q.pop();
            for(int i=0; i<100; i++){
                trie* nxt = cur->children[i];
                if(!nxt) 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;
                }
                nxt->isEnd |= nxt->prv->isEnd;
                q.push(nxt);
            }
        }

        int ans = 0;
        getchar();
        while(m--){
            char str[102];
            fgets(str,101,stdin);
            str[strlen(str)-1]=0;
            trie* cur = rt;
            for(int i=0;i<strlen(str);i++){
                int id = str[i]-32;
                while(cur!=rt && cur->children[id]==nullptr) 
                    cur=cur->prv;
                if(cur->children[id]) 
                    cur=cur->children[id];
                if(cur->isEnd){
                    ans++;
                    cur=rt;  // 찾은 키워드의 마지막을 지우고 새로이 검색을 시작!
                }
            }
        }

        printf("%d\n",ans);
        delete rt;
    }
    return 0;
}