[BOJ/Platinum 2] 백준 5735 Emoticons :-)(C++)

문제 링크

https://www.acmicpc.net/problem/5735

5735번: Emoticons :-)

 

 

문제

이모티콘은 채팅과 이메일에서 단어로 표현할 수 없는 감정을 나타내기 위해 종종 쓰인다. 이는 다양한 면에서 장점이 있지만, 많은 사람들은 이모티콘을 매우 짜증난다고 여기며, 없애고 싶어한다.

세종이가 딱 그렇다. 세종이는 이모티콘을 너무 싫어한 나머지, 전세계의 이메일에서 이모티콘을 없애버릴 계획을 세웠다. 당신은 세종이와 계획을 함께 준비하고 있어서, 세종이를 도와줄 특별한 프로그램을 제작하려고 한다.

프로그램은 제거할 이모티콘의 리스트를 먼저 받는다. 각 이모티콘은 공백(whitespace)을 포함하지 않은 문자열이다. 또한 몇몇 텍스트도 함께 받는다. 이때 프로그램이 해야 할 일은 텍스트의 몇몇 글자를 공백으로 바꿔서 원래 존재하던 모든 이모티콘을 없애버리는 것이다. 원래 텍스트의 한 줄에만 걸쳐 나타나며, 사이에 다른 공백이나 문자열이 끼어 있지 않은 이모티콘만을 이모티콘이라고 할 것이다.

세종이의 계획을 최대한 들통나지 않게 하기 위해, 당신은 공백으로 대체할 문자의 개수를 최소한으로 해야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 여러 줄로 이루어져 있다. 첫 번째 줄은 이모티콘의 개수 N과 텍스트 줄 수 M이 주어지며, 다음 N개의 줄에는 15글자 이하의 비어 있지 않은 문자열인 각 이모티콘이 주어진다. 그 다음 M개의 줄에는 이모티콘을 지울 텍스트들이 주어지며 80글자 이하이다. 1 ≤ N, M ≤ 100 이라 가정해도 좋다.

이모티콘은 영어 대소문자, 숫자, 그리고 특수문자 “!?.,:;-_'#$%&/=*+(){}[]”(큰따옴표는 포함되지 않음)로만 구성될 수 있다. 텍스트는 여기에 추가로 공백문자까지 포함할 수 있다.

입력의 끝에는 N = M = 0이 주어진다.

출력

각 테스트 케이스에 걸쳐, 한 줄에 하나씩 공백으로 대체해야 할 문자의 최소 개수를 출력한다.

예제 입력 1

4 6
:-)
:-(
(-:
)-:
Hello uncle John! :-) :-D
I am sad or happy? (-:-(?
I feel so happy, my head spins
(-:-)(-:-)(-:-)(-:-) :-) (-: :-)
but then sadness comes :-(
Loves you, Joanna :-)))))
3 1
:)
):
))
:):)):)):)):(:((:(((:):)
0 0

예제 출력 1

11
8

알고리즘 분류

• 트라이
• kmp

풀이

N개의 이모티콘을 트라이에 insert한다. 그리고 M개의 텍스트를 탐색하면서 이모티콘을 발견하면 제거한다.

이모티콘을 제거하는 과정은 트라이 내부에서 이모티콘을 검색하고 이모티콘을 찾으면 카운트를 한 후 다시 루트 노드로 돌아간다.

루트 노드로 돌아가지 않을 시 이모티콘을 지웠다고 간주되지 않기 때문이다.

즉 하나의 이모티콘이 검색되었다면, 그 이모티콘을 공백으로 바꾸었다고 치고 다시 다른 이모티콘을 검색하기 위해 루트 노드로 돌아가는 것이다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct TRIE {
    string Prefix;
    bool isEnd;
    map<char, TRIE*> ChildTrie;
    TRIE* FailLink;

    TRIE() : isEnd(false), FailLink(nullptr){}

    void insert_Pattern(string Pattern) {
        TRIE* NowTrie = this;
        for (int i = 0; i < Pattern.size(); i++) {
            if (NowTrie->ChildTrie.find(Pattern[i]) == NowTrie->ChildTrie.end()) {
                NowTrie->ChildTrie[Pattern[i]] = new TRIE;
            }

            NowTrie = NowTrie->ChildTrie[Pattern[i]];
        }
        NowTrie->Prefix = Pattern;
        NowTrie->isEnd = true;
    }

    void find_FailLink() {
        TRIE* StartTrie = this;
        queue<TRIE*> Q;
        Q.push(StartTrie);

        while (!Q.empty()) {
            TRIE* NowTrie = Q.front();
            Q.pop();

            for (auto& IT : NowTrie->ChildTrie) {
                TRIE* NextTrie = IT.second;

                if (NowTrie == StartTrie) {
                    NextTrie->FailLink = StartTrie;
                }
                else {
                    TRIE* PrevTrie = NowTrie->FailLink;
                    while ((PrevTrie != StartTrie) && (PrevTrie->ChildTrie.find(IT.first) == PrevTrie->ChildTrie.end())) {
                        PrevTrie = PrevTrie->FailLink;
                    };

                    if (PrevTrie->ChildTrie.find(IT.first) != PrevTrie->ChildTrie.end()) {
                        PrevTrie = PrevTrie->ChildTrie[IT.first];
                    }

                    NextTrie->FailLink = PrevTrie;
                }
                if (NextTrie->FailLink->isEnd) {
                    NextTrie->isEnd = true;
                }
                Q.push(NextTrie);
            }

        };
    }
};

int N, M;
string S;
int Answer;

int kmp(string Now, TRIE* Root) {
    TRIE* NowTrie = Root;
    int Result = 0;
    for (int i = 0; i < Now.size(); i++) {
        while ((NowTrie != Root) && (NowTrie->ChildTrie.find(Now[i]) == NowTrie->ChildTrie.end())) {
            NowTrie = NowTrie->FailLink;
        };

        if (NowTrie->ChildTrie.find(Now[i]) != NowTrie->ChildTrie.end()) {
            NowTrie = NowTrie->ChildTrie[Now[i]];
        }
        
        if (NowTrie->isEnd) {
            Result++;
            NowTrie = Root;
        }
    }

    return Result;
}

void find_Answer() {
    TRIE* Root = new TRIE();
    for (int i = 0; i < N; i++) {
        cin >> S;
        Root->insert_Pattern(S);
    }
    Root->find_FailLink();
    Answer = 0;
    cin.ignore();
    for (int i = 0; i < M; i++) {
        getline(cin, S);
        Answer += kmp(S, Root);
    }
    cout << Answer << "\n";
}

void input() {
    while (1) {
        cin >> N >> M;
        if ((N == 0) && (M == 0)) {
            break;
        }
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}