[BOJ] 16916. 부분 문자열 (C++)

문제

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 확인

생각할 것

• 문자열 검색 시 시간복잡도를 줄이기 위해 KMP를 사용하자!
• 실패했던 반례 :

baekjoon
baekjoon1

• 원인
  • 검색 시 while(begin ≤ S.size() - P.size()) 으로 탐색을 했는데, 패턴이 더 긴 경우에는 음수가 되므로 끝나지 않는다.
• 해결 방법
  • 패턴이 더 긴 경우에는 반드시 일치하는 결과를 얻을 수 없으므로 조건을 추가해준다

코드

1. 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, P;
    cin >> S;
    cin >> P;

    // 0. 패턴이 더 긴 경우에는 부분 문자열을 찾을 수 없음
    if(S.size() < P.size()){
        cout << 0;
        return 0;
    }

    // 1. pi 배열 완성하기
    vector<int> pi(P.size());
    int begin = 1, matched = 0;
    while (begin + matched < P.size()) {
        if (P[matched] == P[begin + matched]) { // 양끝 일치
            ++matched;
            pi[begin + matched - 1] = matched;
        } else {
            if (matched == 0) ++begin; // 하나도 일치하지 않을 시
            else {
                begin += (matched - pi[matched - 1]);
                matched = pi[matched - 1];
            }
        }
    }

    // 2. 검색
    begin = 0, matched = 0;
    while (begin <= S.size() - P.size()) { // 패턴이 더 짧은 경우에만 해당!
        if (matched < P.size() && S[begin + matched] == P[matched]) {
            ++matched;
            if (matched == P.size()) {
                cout << 1;
                return 0;
            }
        } else {
            if (matched == 0) ++begin;
            else {
                begin += (matched - pi[matched - 1]);
                matched = pi[matched - 1];
            }
        }
    }

    cout << 0;
    return 0;
}

 

2. 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, P;
    cin >> S;
    cin >> P;

    // 1. pi 배열 완성하기
    vector<int> pi(P.size());
    int matched = 0;
    for (int i = 1; i < P.size(); i++) { // i는 begin + matched에 해당
        while (matched > 0 && P[i] != P[matched]) matched = pi[matched - 1]; // 현재 문자가 다르면 matched를 pi[matched - 1]로
        if (P[i] == P[matched]) pi[i] = ++matched; // 동일하면  matched를 1 더해줌
    }

    // 2. 검색
    matched = 0;
    for (int i = 0; i < S.size(); i++) { // i는 begin + matched에 해당
        while (matched > 0 && S[i] != P[matched]) matched = pi[matched - 1]; // 현재 문자가 다르면 matched를 pi[matched - 1]로
        if (S[i] == P[matched]) ++matched; // 동일하면  matched를 1 더해줌
        if (matched == P.size()) { // 이때 패턴 개수와 동일하면 문자열을 발견
            cout << 1;
            return 0;
        }
    }

    cout << 0;
    return 0;
}