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

문제

숫자가 섞여있는 문자열에서 원하는 알파벳 문자열 찾기

생각할 것

문자열 검색이니 KMP를 사용해보자

알파벳 위치 필요 없이 존재여부만 알면 되므로 숫자를 다 없애고 비교하자

코드

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

using namespace std;

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

    string S, K;
    cin >> S >> K;

    string Str;
    for (int i = 0; i < S.size(); i++) {
        if (!('0' <= S[i] && S[i] <= '9')) Str += S[i];
    }

    vector<int> pi(K.size()); // prefix index
    int matched = 0;
    for (int i = 1; i < K.size(); i++) { // 1부터 시작
        while (matched > 0 && K[i] != K[matched]) matched = pi[matched - 1]; // matched > 0 이고 다르면
        if (K[i] == K[matched]) pi[i] = ++matched; // 같으면
    }

    matched = 0;
    for (int i = 0; i < Str.size(); i++) {
        while (matched > 0 && Str[i] != K[matched]) matched = pi[matched - 1];
        if (Str[i] == K[matched]) ++matched;
        if (matched == K.size()) {
            cout << 1;
            return 0;
        }
    }

    cout << 0;
    return 0;
}