백준 알고리즘 1786번 : 찾기

링크

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

sol1) KMP

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;

struct KMP{
  vector<int> failure(string &S){
    vector<int> f(S.size());
    int j = 0;
    for(int i = 1; i < S.size(); i++){
      while(j > 0 && S[i] != S[j]) j = f[j - 1];
      if(S[i] == S[j]) f[i] = ++j;
    }
    return f;
  }
  vector<int> FindString(string &A, string &B){
    vector<int> ret;
    vector<int> f = failure(B);
    int j = 0;
    for(int i = 0; i < A.size(); i++){
    while(j > 0 && A[i] != B[j]) j = f[j - 1];
    if(A[i] == B[j]) j++;
        if(j == B.size()){
          ret.push_back(i + 2 - B.size());
          j = f[j - 1];
      }
    }
    return ret;
  }
}KMP;

int32_t main(){
  fastio;
  string A,B; getline(cin, A);
  getline(cin, B);
  auto ret = KMP.FindString(A,B);
  cout << ret.size() << "\n";
  for(auto& c : ret) cout << c << ' ';
}