#include <bits/stdc++.h>
using namespace std;

// 종만북 부분 일치 테이블
vector<int> getPartialMatch(const string& N)
{
int m = N.size();
 vector<int> pi(m, 0);

 int begin = 1, matched = 0;

 while(begin + matched < m){
if(N[begin+matched] == N[matched]){
++matched;
 pi[begin+matched-1] = matched;
 }
else{
if(matched==0)
++begin;
 else{
begin += matched - pi[matched-1];
 matched = pi[matched-1];
 }
}
}

return pi;
}

int solution(string s, string t){
vector<int> pi = getPartialMatch(t);
 int ret = 0, matched = 0, S = s.size(), T = t.size();
 int i = S > T ? S-T : 0, vt = T > S ? S : T;
 while(i<S){
if(i+matched == S){
++ret;
 i += matched - pi[matched-1];
 vt -= (matched-pi[matched-1]);
 matched = pi[matched-1];
 }
else if(s[i+matched]!=t[matched]){
if(matched == 0){
++i;
 --vt;
 }
else{
i += matched - pi[matched-1];
 vt -= (matched-pi[matched-1]);
 matched = pi[matched-1];
 }
}
else{
++matched;
 if(matched == vt){
++ret;
 i += matched - pi[matched-1];
 vt -= (matched-pi[matched-1]);
 matched = pi[matched-1];
 }
}
}

return ret;
}

int main()
{
string s = "abcdaabbaa", t = "aabbaabbba";
 cout << solution(s, t) << "\n";
 return 0;
}


다른 사람 코드에서 KMP 쓰는거 보고 부랴부랴 종만북 펴서 풀어봤는데


한 6시간 걸린듯


이런 문제를 어떻게 30분 안에 풀지 


십고수들 너무 무서워