백준 1786

1786번: 찾기

KMP 알고리즘이란,, 문자열 패턴 매치 알고리즘임

다만 찾는 문자열과 패턴 문자열을 전부 탐색하지 않는다는 점에서 시간복잡도가 급격히 줄어듦.

전체 솔루션을 정리하자면, 실패함수를 구한 후, kmp를 돌려서 패턴 하나를 전부 찾았을 때 카운트를 증가시키고 패턴 시작 위치를 큐에 푸쉬함.

실패함수 찾는 코드

void failfun(){
    for(int i=1,j=0; i<p.length(); i++){
        while (j>0 && p[i]!=p[j]){
            j=fail[j-1];
        }
        if (p[i]==p[j])
            fail[i]=++j;
        else
            fail[i]=0;
    }
}

패턴이 앞에 존재하지 않으면 (j==0) fail[j]=0

패턴과 동일 할 경우 fail[i]=++j를 해준다.

kmp 함수 코드

void kmp(){
    for (int i=0,j=0; i<s.length(); i++){
        while(j>0 && s[i]!=p[j]){
            j=fail[j-1];
        }
        if(s[i]==p[j]){
            if (j == (p.length()-1)){
                q.push(i-p.length()+2);
                cnt++;
                j = fail[j];
            }
            else
                j++;
        }
    }
}

만약 패턴을 다 찾았다면 카운트를 증가시키고 시작위치를 푸쉬한다.