[BOJ 16172 // C++] 나는 친구가 적다 (Large)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16172번 문제인 나는 친구가 적다 (Large)이다.
문제는 아래 링크를 확인하자.

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

16172번: 나는 친구가 적다 (Large)

주어진 길이 N의 문자열에서 주어진 길이 K의 키워드가 있는지 탐색하는 것은 KMP 알고리즘을 이용해 O(N+M)만에 해낼 수 있다. KMP 알고리즘을 구현하여 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>;
using namespace std;

int pi[200000];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string SS, S = "", s; cin >> SS >> s;
    int LL = (int)SS.length();
    for (int i = 0; i < LL; i++) {
        if (SS[i] >= '0' && SS[i] <= '9') continue;
        S += SS[i];
    }
    int L = (int)S.length();
    int l = (int)s.length();

    for (int i = 0; i < l; i++) {
        int idx = i;
        while (1) {
            if (idx == 0) break;
            if (s[pi[idx - 1]] == s[i]) break;
            idx = pi[idx - 1];
        }
        if (idx == 0) continue;
        pi[i] = pi[idx - 1] + 1;
    }
    int matching = 0; bool chk = 0;
    for (int i = 0; i < L; i++) {
        if (S[i] == s[matching]) {
            matching++;
            if (matching == l) {
                chk = 1;
                break;
            }
        }
        else {
            if (matching == 0) continue;
            matching = pi[matching - 1];
            i--;
        }
    }
    if (chk) cout << 1;
    else cout << 0;
    return 0;
}