[BOJ/Platinum 1] 백준 2809 아스키 거리(C++)

문제 링크

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

2809번: 아스키 거리

 

문제

상근이네 집 앞의 아스키 거리는 알파벳 소문자가 적혀 있는 타일 N개로 이루어져 있다. 정부는 알 수 없는 이유 때문에 거리의 타일을 자주 바꾼다. 하지만, 글자가 적혀있는 타일은 공급이 수요를 따라갈 수 없기 때문에 정부는 M종류의 묶음 타일만 사용할 수 있다.

i번째 묶음 타일은 Li개의 글자로 이루어져 있다. 묶음 타일은 회전하거나 조각으로 나눌 수 없다. 또, 거리와 연속해서 글자가 모두 일치하는 경우에만 그 묶음을 사용해서 타일을 교체할 수 있다. 타일은 겹쳐도 상관없고, 한 묶음을 여러 번 사용해도 된다.

현재 거리에 쓰여 있는 타일과 묶음 타일의 정보가 주어졌을 때, 그 어떤 타일로도 바꿀 수 없는 칸의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 거리의 길이 N이 주어진다. 다음 줄에는 거리에 원래 적혀져있는 알파벳이 주어진다. 셋째 줄에는 묶음 타일의 종류의 개수 M이 주어진다. 다음 M개 줄에는 각 묶음 타일에 적혀져있는 알파벳이 주어진다. (1 ≤ N ≤ 300,000, 1 ≤ M ≤ 5000, 1 ≤ 각 묶음 타일의 길이 ≤ 5000)

출력

첫째 줄에 그 어떤 묶음 타일로도 바꿀 수 없는 타일의 개수를 출력한다.

예제 입력 1

6
abcbab
2
cb
cbab

예제 출력 1

2

예제 입력 2

4
abab
2
bac
baba

예제 출력 2

4

예제 입력 3

6
abcabc
2
abca
cab

예제 출력 3

1

알고리즘 분류

• 트라이
• kmp

풀이

M개의 타일을 트라이에 insert한다. 이 때, 각 타일의 길이를 저장하고, 타일의 끝에 타일의 번호를 기록해둔다.

그리고 실패 함수를 수행하면서 현재 노드의 Fail Link로 연결된 노드가 타일의 끝일 경우, 즉 번호가 0 이상인 경우 현재 타일의 번호도 Fail Link로 연결된 노드의 번호로 초기화해준다. 현재 노드가 타일의 끝인 경우에는 Fail Link로 연결된 타일의 길이가 현재 타일의 길이보다 길 경우 현재 노드의 번호를 Fail Link로 연결된 타일의 번호로 바꿔준다.

이제 원래 적힌 문자열에서 타일이 존재하는지를 탐색한다. 현재 노드의 번호가 0 이상인 경우, 즉 타일의 끝인 경우 현재 문자부터 역순으로 타일의 개수만큼의 문자를 전부 교체할 수 있는 문자라고 기록해둔다.

마지막으로 교체가 불가능한 문자들의 개수를 구하여 출력한다.

코드

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

using namespace std;
int Tile_Length[MAX_T];

struct TRIE {
    int isEnd;
    int Prefix;
    vector<pair<char, TRIE*> > Child;
    TRIE* Fail;

    TRIE() {
        Prefix = -1;
        isEnd = -1;
        Child.clear();
        Fail = nullptr;
    }

    void insert_Pattern(string Pattern, int Index) {
        TRIE* NowTrie = this;

        for (int i = 0; i < Pattern.size(); i++) {
            char Now = Pattern[i];

            bool Flag = false;
            for (auto IT : NowTrie->Child) {
                if (IT.first == Now) {
                    Flag = true;
                    NowTrie = IT.second;
                    break;
                }
            }
            if (!Flag) {
                NowTrie->Child.push_back(make_pair(Now, new TRIE));
                NowTrie = NowTrie->Child.back().second;
            }
        }
        NowTrie->Prefix = Pattern.size();
        NowTrie->isEnd = Index;
    }

    void find_Fail() {
        TRIE* RootTrie = this;
        queue<TRIE*> Q;
        Q.push(RootTrie);

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

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

                if (NowTrie == RootTrie) {
                    NextTrie->Fail = RootTrie;
                }
                else {
                    TRIE* PrevTrie = NowTrie->Fail;

                    while (PrevTrie != RootTrie) {
                        bool Flag = false;
                        for (auto A : PrevTrie->Child) {
                            if (A.first == IT.first) {
                                Flag = true;
                                break;
                            }
                        }
                        if (Flag) {
                            break;
                        }
                        PrevTrie = PrevTrie->Fail;
                    };
                    for (auto A : PrevTrie->Child) {
                        if (A.first == IT.first) {
                            PrevTrie = A.second;
                            break;
                        }
                    }
                    NextTrie->Fail = PrevTrie;
                }
                if (NextTrie->Fail->isEnd >= 0) {
                    if ((NextTrie->isEnd == -1) || (Tile_Length[NextTrie->Fail->isEnd] > Tile_Length[NextTrie->isEnd])) {
                        NextTrie->isEnd = NextTrie->Fail->isEnd;
                    }
                }
                Q.push(NextTrie);
            }
        };
    }
};

int N, M;
string First, S;
bool Visited[MAX];

int kmp(TRIE* Root) {
    TRIE* NowTrie = Root;
    int Answer = 0;

    for (int i = 0; i < First.size(); i++) {
        char Now = First[i];

        while (NowTrie != Root) {
            bool Flag = false;
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    Flag = true;
                    break;
                }
            }
            if (Flag) {
                break;
            }
            NowTrie = NowTrie->Fail;
        };
        for (auto A : NowTrie->Child) {
            if (A.first == Now) {
                NowTrie = A.second;
                break;
            }
        }
        if (NowTrie->isEnd >= 0) {
            int Len = Tile_Length[NowTrie->isEnd];
            for (int j = i; j > (i - Len); j--) {
                Visited[j] = true;
            }
        }
    }
    for (int i = 0; i < First.size(); i++) {
        if (!Visited[i]) {
            Answer++;
        }
    }

    return Answer;
}

void input() {
    TRIE* Root = new TRIE();
    cin >> N;
    cin >> First;
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> S;
        Tile_Length[i] = S.size();
        Root->insert_Pattern(S, i);
    }
    Root->find_Fail();
    cout << kmp(Root) << "\n";
    delete Root;
}

int main() {
    FASTIO
    input();

    return 0;
}