[백준] 16916번* (KMP 알고리즘)

💻 C++ 기반

부분 문자열
https://www.acmicpc.net/problem/16916

✔️ KMP 알고리즘
: Knuth-Morris-Pratt 이 3명의 사람이 개발한 알고리즘

• 문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘의 하나
• 문자열 검색 시 불필요한 문자간 비교를 없애기 위해 실패함수 (pi)를 사용
• 아이디어가 이해가 안되면? -> 강의 참고
• 코드가 이해가 안되면? -> 강의 참고

#include <iostream>
#include <string>
#include <vector>

#define MAX 1000001

using namespace std;

vector<int> makeTable(string pattern)
{
    int patternSize = pattern.length();
    vector<int> table(patternSize, 0);
    int j = 0;
    for (int i = 1; i < patternSize; i++)
    {
        while (j > 0 && pattern[i] != pattern[j])
        {
            j = table[j - 1];
        }
        if (pattern[i] == pattern[j])
        {
            table[i] = ++j;
        }
    }
    return table;
}

void KMP(string parent, string pattern)
{
    vector<int> table = makeTable(pattern);
    int parentSize = parent.length();
    int patternSize = pattern.length();
    int j = 0;
    for (int i = 0; i < parentSize; i++)
    {
        while (j > 0 && parent[i] != pattern[j])
        {
            j = table[j - 1];
        }
        if (parent[i] == pattern[j])
        {
            if (j == patternSize - 1)
            {
                j = table[j];
                cout << 1;
                return;
            }
            else
            {
                j++;
            }
        }
    }
    cout << 0;
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    string S, P;
    cin >> S >> P;
    
    KMP(S, P);
    
    return 0;
}