[백준] 16916 부분 문자열

May 25, 2021 ( last updated : May 25, 2021 )
KMP 알고리즘

https://github.com/sneakstarberry/

Abstract

[백준] 16916번 부분 문자열

[백준] 16916번 부분 문자열

백준 16916번

알고리즘 유형

풀이방법

KMP 알고리즘을 이용해서 풀어야한다. KMP를 통해서 match된 글자 갯수를 쉽게 구할 수 있다. 이를 통해서 크기가 0인지 0보다 큰지 확인해서 0 또는 1을 출력한다.

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

using namespace std;

string S, P;

vector<int> getPartialMatch(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;
}

vector<int> kmpSearch(string &src, string &search) {
  int n = src.size(), m = search.size();
  vector<int> ret;
  vector<int> pi = getPartialMatch(search);
  int begin = 0, matched = 0;

  while (begin <= n - m) {
    if (matched < m && src[begin + matched] == search[matched]) {
      ++matched;

      if (matched == m) {
        ret.push_back(begin);
      }
    } else {
      if (matched == 0) {
        ++begin;
      } else {
        begin += matched - pi[matched - 1];
        matched = pi[matched - 1];
      }
    }
  }

  return ret;
}

int main() {
  cin >> S;
  cin >> P;

  vector<int> result = kmpSearch(S, P);
  if (result.size() >= 1) {
    cout << 1;
  } else if (result.size() == 0) {
    cout << 0;
  }
  return 0;
}

Originally published May 25, 2021
Latest update May 25, 2021

Related posts :

{# #}