KMP 알고리즘

문제

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

16916번: 부분 문자열

#include <iostream>
#include <vector>
using namespace std;
string p, s;
vector<long long> pi((1e6) + 1);
void make_pi(string p) {
    // i는 접두사, j는 접미사 인덱스
    // pi 배열은 접두사와 접미사가 일치하는 최대 길이
    long long i = 0, j = 1;
    long long p_len = p.length();
    pi[0] = 0;

    while(j < p_len) {
        if(p[i] == p[j]) {
            pi[j++] = ++i;
        }
        else {
            if(i == 0) {
                pi[j++] = 0;
            }
            else {
                // 이미 이전에 일치한 전적이 있다는 뜻이기 때문에 활용
                // pi 배열에는 문자열 길이가 저장되기 때문에 pi[i -1]은 이미 검증된 공통 문자열의 다음 인덱스를 가리킴
                i = pi[i - 1];
            }
        }
    }
}

bool kmp() {
    long long s_len = s.length();
    long long p_len = p.length();

    int i = 0, j = 0;
    while(i < s_len) {
        if(s[i] == p[j]) {
            i++;
            j++;
            // 패턴 발견
            if(j == p_len) {
                return true;
            }
        }
        else {
            if(j != 0) {
                j = pi[j - 1];
            }
            else {
                i++;
            }
        }
    }

    return false;
}
int main() {
    cin >> s >> p;

    long long s_len = s.length();
    long long p_len = p.length();

    if(s_len < p_len) {
        cout << 0 << '\n';
        return 0;
    }

    make_pi(p);
//    for(int i = 0;i < p_len;i++) {
//        cout << pi[i];
//    }
    bool result = kmp();
    if(result) {
        cout << 1 << '\n';
    }
    else {
        cout << 0 << '\n';
    }
    return 0;
}

참고

https://chanhuiseok.github.io/posts/algo-14/

알고리즘 - KMP 알고리즘 : 문자열 검색을 위한 알고리즘

https://injae-kim.github.io/dev/2020/07/23/all-about-kmp-algorithm.html

Injae's devlog

https://bblackscene21.tistory.com/2

[알고리즘 공부] KMP Algorithm (문자열 검색 알고리즘)