kmp 인사이트

싸지방에서 코포 치다가 kmp를 만났다.

사회에 있을 때도 많이 안 해봐서 서툴렀던 건데, 이 참에 제대로 기록해두려고 한다.

 

kmp는 에디터를 켜서 주어진 문자열의 모든 prefix를 적고 그 안에서 ctrl + f를 하는 느낌이다.

 

문자열 "ababacabababc"를 상상해보자.

 

윗쪽은 이럴 것이다:

빨간 부분이 윗쪽에서 ctrl + f 했을 때 선택될 수 있는 영역을 나타낸다.

 

빨간 부분을 쭉 사용하다가, "ababab"가 나오며 흐름이 끊긴걸 확인할 수 있다.

하지만 여기서 재활용을 하는데, "abab"로 이어갈 수 있기 때문이다.

 

근데 "abab"를 써먹을 수 있음을 amortized O(1)에 어떻게 확인할텐가?

"ababa"의 뒷부분의 빨간 영역을 새로 따라가서 연장 가능함을 확인하면 된다.

 

그래서 선택된 영역을 두 칸 줄이게 된다.

선택된 범위는 줄어들거나, 1씩 늘어나기만 한다.

amortized O(n)이라는 의미이다.

 

"ababacababab" FAIL → "ababab" OK

이런 느낌?

 

 

느낌은 이렇게 기억해두고...

$\pi(i) := \max \{k | k<i \text{ and } S[1 : k] = S[k-i+1 : n] \}$라고 정의를 잘 해보자.

 

코드는 그럼 다음과 같이 짤 수 있게 된다.

ll drag = 0;
border[0] = -1;
border[1] = 0;
            
for(int i=2; i<=n; ++i) {
    while (drag>=0 && a[drag+1] != a[i]) {
        drag = border[drag];
    }
    if (drag>=0)
        border[i] = ++drag;
    else
        border[i] = drag = 0;
}