[백준 1786] 찾기

분류 : KMP

 

요구사항

Kmp를 사용하여 T문자열에 P가 몇번 나타나는지 출력

 

풀이

단순히 n*m으로 풀면 시간초과가 난다

kmp라는 O(n+m)이라는 시간복잡도를 가진 알고리즘 풀이한다

 

pi는 p배열이 현재 길이에서 몇개까지의 접두사와 접미사 같은지 저장해놓은 함수이다

while(j>0 && n[i] != m[j]) j=pi[j-1];

while(j>0 && m[i] !=m[j]) j= pi[j-1];

 

이 두 부분은 같은 문자열을 찾았으면 똑같은거를 반복해서 찾지 않기위해

 

현재 i에서 부터 j를 변화시켜 몇개까지가 맞는가 확인하는것이다.

 

처음 접하는 문제라서 어렵다

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <string>
using namespace std;
int ans[1000100];
int pi[1000100];
string n;
string m;
int cnt=0;
void GetPi(){
    int msize = m.size();
    for(int i=1 ,j=0; i< msize ; i++){
        while(j>0 && m[i] !=m[j]) j= pi[j-1];
        if(m[i] == m[j]){
            pi[i]=++j;
        }
    }
}

void kmp(){
    int nsize = n.size();    
    int msize = m.size();
    cnt=0;
    for(int i=0, j=0 ; i < nsize ; i++){
       // cout<<"i"<<i<<endl;
        while(j>0 && n[i] != m[j]) j=pi[j-1];

        if(n[i] == m[j]){
            if(j==msize-1){
               // cout<<"!@#"<<endl;
                ans[cnt++]=i-msize+2;
                j=pi[j];
            }
            else j++;
        }
    }
}



int main(){
    getline(cin,n);
    getline(cin,m);
    GetPi();
    kmp();
  
    cout<<cnt<<endl;
    for(int i=0 ; i <cnt ; i++){
        cout<<ans[i]<<'\n';
    }
}