문제 푼 날짜 : 2021-09-26

문제

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

접근 및 풀이

KMP 알고리즘을 적용하여 푸는 문제였습니다.
알고리즘에 대한 학습만 되어 있다면 쉬운 문제였습니다.
KMP 알고리즘에 대한 자세한 설명은 이 곳에 아주아주 잘 되어있어 참고하시면 해결하는데 도움이 될 것입니다.

코드

// 백준 16916번 : 부분 문자열
#include <iostream>
#include <vector>

using namespace std;

vector<int> makeTable(string pattern) {
    vector<int> table(pattern.size(), 0);

    for (int i = 1, j = 0; 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;
}

bool KMP(string text, string pattern) {
    vector<int> table = makeTable(pattern);

    for (int i = 0, j = 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) {
                return true;
                j = table[j];
            } else {
                j++;
            }
        }
    }
    return false;
}

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

    if (KMP(text, pattern)) {
        cout << 1;
    } else {
        cout << 0;
    }
    return 0;
}

결과

피드백

특정 알고리즘을 적용해야 풀리는 문제를 보고, 그대로 적용해서 풀었을 때의 즐거움이란..ㅎ