[C++] 백준 1786번: 찾기

문제링크

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

풀이방법

해당 문제는 구현된 실패 함수를 기반으로 KMP 알고리즘을 만드는 가장 기본적인 문제이다. 문자열의 각 문자들을 전부 탐색하여 문자열을 비교하는 알고리즘의 시간 복잡도인 O(N*M)을 O(N+M)으로 만들어주는 문자열 비교 알고리즘이다. 해당 내용을 모른다면 아래 바킹독님 알고리즘 영상과 구글링을 통해서 내용을 이해하고 공부하자.

추가적으로 공백이 포함된 문자열을 받아야 하기 때문에 getline을 활용한다. 또한 BOJ 16916과 다르게 일치하는 문자열을 찾아도 계속 진행해야 하기 때문에 j = f[j-1]로 변경하여 다시 문자열 탐색을 시작한다.

https://www.youtube.com/watch?v=9bkbV-VANQ0

코드

// Authored by : scsc3204
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/2396665d65a7478c95fadcb70a0236ab
#include 
using namespace std;

string t, p;
vector f, ans;

vector failure(){
  vector f(p.size());
  int j = 0;
  for(int i = 1; i < (int)p.size(); i++){
    while(j > 0 && p[i] != p[j]) j = f[j-1];
    if(p[i] == p[j]) f[i] = ++j;
  }
  return f;
}

void solve(){
  int j = 0;
  for(int i = 0; i < (int)t.size(); i++){    
    while(j > 0 && t[i] != p[j]) j = f[j-1];
    if(t[i] == p[j]) j++;
    if(j == (int)p.size()){
      ans.push_back(i + 1 - j);
      j = f[j-1];
    }
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  getline(cin, t);
  getline(cin, p);

  f = failure();
  solve();

  cout << ans.size() << '\n';
  for(int a : ans) cout << (a + 1) << ' ';
}
/*
t와 p 모두 공백이 포함된 문자열을 받아야 하기 때문에
getline을 활용한다.

BOJ 16916과 다르게 일치하는 문자열을 찾아도 계속 진행해야 하기 때문에
j = f[j-1]로 변경한다.
*/