(1786) 찾기

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

단계별로 풀어보기

46단계(문자열 알고리즘 1) 1번째

 

 

 

더도 말고 덜도 말고 KMP 알고리즘을 요구하는 문제.

문자열 T에서 문자열 P가 있는지 찾는다고 하자. T의 x번째 문자에서 대조를 시작했는데 P의 y번째 문자에서 틀렸다면, T의 x번째 문자부터 x+y-2번째 문자까지는 P의 1번째 문자부터 y-1번째 문자까지와 같다는 것이다. 따라서 T의 x+1번째부터 다시 대조하지 않고 이 정보를 최대한 이용하는 것이 KMP이다. P의 1~y-1번째 부분문자열에서 Pi(y-1)개 길이의 접두사와 접미사가 일치한다면 앞쪽 접두사만큼의 정답 확인은 건너뛸 수 있다(어차피 같으므로). 만약 점프한 지점에서도 문자가 다르다면 다시 해당 위치의 Pi를 참조해 가능한 만큼 건너뛴다. P와 일치하는 경우에도 마지막 문자열까지 같다는 정보를 이용하면 이후 문자열을 찾을 수 있다.

이제 실패함수 Pi를 찾아야 하는데, 나이브하게 찾으면 P의 길이가 M일 때 O(M^3)가 걸린다. 실생활에서 T에 비해 P는 매우 짧으므로 그냥 구해도 상관없지만 PS에서는 무조건 T길이≒P길이 수준의 저격 데이터가 있을 것이므로 KMP의 원리를 이용해 Pi를 찾는 과정도 O(m)으로 줄일 수 있다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  string t, p;
  
  getline(cin, t);
  getline(cin, p);
  
  int tlen= t.length(), plen= p.length();
  
  vector<int> fail(plen), ans;
  
  for(int i=1,j=0;i<plen;i++){
    while(j>0 && p[i]!=p[j])  j= fail[j-1];
    
    if(p[i]==p[j])  fail[i]= ++j;
  }
  
  for(int i=0,j=0;i<tlen;i++){
    while(j>0 && t[i]!=p[j])  j= fail[j-1];
    
    if(t[i]==p[j]){
      if(j==plen-1){
        ans.push_back(i-plen+2);
        j= fail[j];
      }else{
        j++;
      }
    }
  }
  
  cout << ans.size() << "\n";
  for(int elem:ans)  cout << elem << " ";
  
  return 0;
}