문제 푼 날짜 : 2021-09-26

문제

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

접근 및 풀이

문자열 검색 알고리즘 중에 KMP(Knuth Morris Partt)알고리즘을 이용하여 푸는 문제였다.
우리가 일반적으로 생각할 수 있는 완전탐색을 통한 문자열 검색 알고리즘은 O(nm) (n : 전체 문자열 길이, m : 찾을 패턴 길이) 의 시간복잡도를 갖도록 구현할 수가 있다.

하지만, 이 알고리즘은 문자열과 패턴의 길이가 길어짐에 따라 그 성능이 아주아주 나빠지게 된다. 이를 개선하기 위해 O(n + m)의 성능을 가지는 것이 바로 KMP 알고리즘이다.
알고리즘을 간단히 설명하자면 매 번 불일치가 일어날때마다, 한 문자(한 칸)씩 당겨가면서 비교하는 것이 아니라, 이미 매칭이 이루어진 부분은 다시 비교하지 않도록 점프하여 새롭게 패턴을 찾아주는 알고리즘이다.

이에 대한 설명은 이 곳에 아주아주 설명이 친절하고 자세히 잘되어있다.
이 곳의 도움을 받아 코드를 작성해보았다.

코드

// 백준 1786번 : 찾기
#include <iostream>
#include <vector>

using namespace std;

vector<int> makeJumpTable(string pattern) {
    vector<int> table(pattern.size(), 0);
    int j = 0;

    for (int i = 1; i < pattern.size(); i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = table[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            table[i] = ++j;
        }
    }
    return table;
}

vector<int> KMP(string text, string pattern) {
    vector<int> table = makeJumpTable(pattern);
    vector<int> ret;
    int j = 0;

    for (int i = 0; i < text.size(); i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = table[j - 1];
        }
        if (text[i] == pattern[j]) {
            if (j == pattern.size() - 1) {
                ret.push_back(i - pattern.size() + 2);
                j = table[j];
            } else {
                j++;
            }
        }
    }
    return ret;
}

int main() {
    string text = "", pattern = "";
    getline(cin, text);
    getline(cin, pattern);

    vector<int> ret = KMP(text, pattern);

    cout << ret.size() << '\n';
    for (int i : ret) {
        cout << i << ' ';
    }
    return 0;
}

결과

피드백

새로운 알고리즘을 배울 때마다 재밌다...ㅎㅎ... 어렵지만,,