[백준] 5525 C++

📌 우선 기껏 풀어놨더니 시간초과 당한 코드

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

// IOIOI
// 시간초과

string ioi(int n) {
  string ioi = "IOI";
  string oi = "OI";

  for(int i=0; i<n-1; i++) {
      ioi += oi;
  }

  return ioi;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  string s;
  string s2;

  int cnt = 0;
  int N, M;

  cin >> N >> M;
  cin >> s;


  string str = ioi(N);


  for(int i=1; i<M; i++) {
    // 문자를 하나씩 돌며 substr함수로 문자열을 잘라 비교함
    if(s.at(i) == 'O') {
      s2 = s.substr(i-1, N*2+1);  // i-1부터 N*2+1만큼 잘라서 s2에 넣음
      if(s2 == str) cnt++;
    }
  }

  cout << cnt << '\n';

  return 0;
}

📌 시간초과로 혼나고 KMP 알고리즘으로 다시 푼 코드

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

// IOIOI
// KMP 알고리즘

string ioi(int n) { // 찾을 문자열을 만드는 함수
  string ioi = "IOI";
  string oi = "OI";

  for(int i=0; i<n-1; i++) {
      ioi += oi;
  }

  return ioi;
}

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]) {  // i와 j 인덱스가 같을 때까지
      j = table[j-1]; // 
    }
    if(pattern[i] == pattern[j]) {
      table[i] = ++j;
    }
  }

  return table;
}

void KMP(string parent, string pattern) {
  int cnt = 0;

  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]) {
      j = table[j-1];
    }
    if(parent[i] == pattern[j]) {
      if(j == patternSize-1) {
        cnt++;
        j = table[j];
      } else {
        j++;
      }
    }
  }
  cout << cnt << '\n';
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  string s;
  string s2;

  int cnt = 0;
  int N, M;

  cin >> N >> M;
  cin >> s; // 주어진 문자열


  string str = ioi(N);  // 찾아야 할 문자열

  KMP(s, str);

  return 0;
}

역시 동빈나 선생님의 KMP 알고리즘 강의를 듣고 나니까 그 전보단 이해가 훨씬 잘 됐다. 근데 혼자서 이렇게 못 짤 것 같은데,,?