[C++] 1786번 찾기 - 문제풀이

● 문제 접근 과정

1. KMP 알고리즘을 써야 풀리는 문제이다.
2. 찾아야하는 문자열에서 반복되는 부분을 찾는다.
3. 이걸 찾으면 탐색으로 하다가 빠르게 넘어 갈 수 있다.
4. 시간복잡도를 O(n)으로 끝낼 수 있다.

● 구현

#include <bits/stdc++.h>
using namespace std;

string n, m;
int result = 0;
vector<int> result_vec;

vector<int> makeTable(string pattern) {
  int patternSize = pattern.size();
  vector<int> table(patternSize, 0);

  int j = 0;
  for (int i = 1; i < patternSize; i++) {
    while (j > 0 && pattern[i] != pattern[j]) {
      j = table[j - 1];
    }
    if (pattern[i] == pattern[j]) {
      table[i] = ++j;
    }
  }
  return table;
}

void kmp(string parent, string pattern) {
  vector<int> table = makeTable(pattern);
  int parentSize = parent.size();
  int patternSize = pattern.size();
  int j = 0;
  for (int i = 0; i < parentSize; i++) {
    while (j > 0 && parent[i] != pattern[j]) {
      //패턴이랑 parent랑 다를 동안에.
      // j 복귀 패턴.
      j = table[j - 1];
    }
    //같을 때.
    if (parent[i] == pattern[j]) {
      //온전하게 패턴 찾았을 때.
      if (j == patternSize - 1) {
        result_vec.push_back(i - patternSize + 2); //어느위치에서 찾았는지
        j = table[j];                              // 패턴 째로 스킵.
        result++;                                  // 몇개 찾았는지.
      } else {
        //단순 매칭.
        j++;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  getline(cin, n);
  getline(cin, m);
  vector<int> table = makeTable(m);
  kmp(n, m);
  cout << result << endl;
  for (int i = 0; i < result_vec.size(); i++) {
    cout << result_vec[i] << " ";
  }
}

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

1786번: 찾기