백준 16916번 부분문자열

부분 문자열 

1 초

512 MB

3992

1271

932

38.672%

문제

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

출력

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

---

kmp알고리즘을 이용하여 풀이하였다. 처음엔 find함수를 썼는데 시간초과가 났다. find 함수는 O(N*M)인데 반해 kmp알고리즘은 O(N+M)이라고 한다. 

백준 1786번 찾기 문제에서 카운트를 빼고 조건충족시 1을 출력해주는것으로 수정하였다.

https://hae-ong.tistory.com/64

백준 1786 찾기

#include<iostream>
#include<string>
#include<vector>
 
using namespace std;
 
string T, P;
 
vector<int> getPartialMatch(const string& N) {
    int m = N.size();
    vector<int> pi(m, 0);

    int begin = 1, matched = 0;

    while (begin + matched < m) {
        if (N[begin + matched] == N[matched]) {
            matched++;
            pi[begin + matched - 1] = matched;
        }
        else {
            if (matched == 0)
                begin++;
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return pi;
}
 
void kmpSearch(const string& H, const string& N) {
    int n = H.size(), m = N.size();
    vector<int> pi = getPartialMatch(N);
   
    int matched = 0;

    for (int i = 0; i < n; i++) {
        while (matched > 0 && H[i] != N[matched])
            matched = pi[matched - 1];
        if (H[i] == N[matched]) {
            matched++;
            if (matched == m) {
                cout << 1;
                return;
            }
        }
    }
    cout << 0;
    return;
}
 
 
 
int main() {
    getline(cin, T);
    getline(cin, P);
    
   
 
    kmpSearch(T,P);
 
    return 0;
}