[C++] 백준 1786번 찾기

문제

T와 P가 주어졌을 때, 문자열 매칭 문제를 해결하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 T가, 둘째 줄에 문자열 P가 주어진다. T와 P의 길이 n, m은 1이상 100만 이하이고, 알파벳 대소문자와 공백으로만 이루어져 있다.

출력

첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 일치한다면, i를 출력하는 식이다.

풀이

kmp알고리즘을 사용해야 시간내에 문제를 해결할 수 있다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

string str;
string target;

vector<int> getPi(){
  int len = target.size();
  int j = 0;
  vector<int> pi(len, 0);
  
  for (int i=1; i<len; i++){
    // j번째가 일치하지 않을 경우 
    // j-1번째일때 pi[j-1]개가 일치함 -> pi[j-1]-1까지 일치
    // j-1번째일때 pi[j-1]째 글자가 i와 일치해야 j-1번째부터 다시 시작할 수 있음
    while (target[i] != target[j] && j > 0)
      j = pi[j-1];

    if (target[i] == target[j]){
      j++;
      pi[i] = j;
    }
  }

  return pi;
}

vector<int> solve(){

  vector<int> ans;
  vector<int> pi = getPi();
  int j = 0;

  for (int i=0; i<str.size(); i++){
    while (str[i] != target[j] && j > 0)
      j = pi[j-1];

    if (str[i] == target[j]){
      if (j == target.length()-1){
        ans.push_back(i-j);
        j = pi[j];
      }
      else{
        j++;
      }
    }
  }

  return ans;
}

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

  // ifstream cin;
  // cin.open("input.txt");

  getline(cin, str);
  getline(cin, target);

  vector<int> ans = solve();

  cout << ans.size() << endl;
  for (auto a: ans)
    cout << a+1 << " ";
}