대2때 배운 KMP를 이제와서 쩔쩔매고있어서, 이번기회에 다시 복습해보았다.
In a Nutshell
- 전체과정
문제:
txt = "AABAACAADAABAABA", pat = "AABA"일 때
과정:
pat으로부터 lps: {0,1,0,1}를 구하고
txt에서 모든 위치 pos: {0,9,12}를 찾는다.
정답:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
txt | A A B A A C A A D A A B A A B A
[0] | - - - -
[9] | - - - -
[12]| - - - -
- 성능
$O(T+P)$ (T:len(txt), P:len(pat))
LPS (Longest proper Prefix Suffix)
KMP 알고리즘은 패턴을 전처리하는 과정이 필요하다.
lps[i]: 패턴의 Substringpat[0..i]에서 Prefix이면서 Suffix도 되는 문자열의 길이
LPS를 구하면 원문에서 탐색할 때 이미 확인한 Suffix만큼 Prefix에서 생략할 수 있다. 예시를 통해 직관을 얻어보자.
예시1: pat = "AABA"
0 1 2 3
pat | A A B A
lps | 0 1 0 1
pat[0..i] |
LPS | lps value |
|
|---|---|---|---|
lps[0] |
A |
0 | |
lps[1] |
AA |
A |
1 |
lps[2] |
AAB |
0 | |
lps[3] |
AABA |
A |
1 |
🤔 그럼 인덱스 포인터 i, j두개를 써서 i는 뒤로 보내면서 Suffix를 찾고, j는 앞에서 Prefix를 찾으면 되지 않을까?
i, j := 1, 0
for i < P {
if pat[i] == pat[j] {
j++ // 문자가 같으면 전진
lps[i] = j
} else {
j = 0 // 문자가 다르면 리셋
lps[i] = 0
}
i++
}
아쉽지만 정답이 아니다. 다음 예시를 보자.
예시2: pat = "AABAAAAB"
0 1 2 3 4 5 6 7
pat | A A B A A A A B
lps | 0 1 0 1 2 2 2 3
- - -
pat[4], pat[5], pat[6]의 값이 2로 이어지는 것을 볼 수 있다. pat[2]에서의 값(B)이 다르기 때문에 Prefix Suffix가 증가하지도, 감소하지도 않는 것이다.
🤔 단순히 j를 전진시키는 것이 아니라, 한칸씩 뒤로 되돌아가는 과정이 필요해보인다.
i, j := 1, 0
for i < P {
if pat[i] == pat[j] {
j++ // 문자가 같으면 전진
lps[i] = j
i++
} else { // 문자가 다르면
if j == 0 {
lps[i] = 0 // 뒤로 갈 곳이 없음
i++
} else {
j-- // 뒤로 한 칸 가기?
}
}
}
그런데 이 코드도 정답이 아니다. 다음 예시를 보자.
예시3: pat = "AABAAAABB"
0 1 2 3 4 5 6 7 8
pat | A A B A A A A B B
lps | 0 1 0 1 2 2 2 3 ?
▲ ▲
j i (mismatch, j = j-1 = 2)
▲ ▲
j i (match?)
j가 한칸 뒤로 가면 pat[2] == pat[8] == 'B'이기 때문에 pat[8] = j+1 = 3이 되어버린다.
왜 이런 일이 발생할까? 뒤로 간다는 명령은 단순히 한 칸 뒤로 가는 것이 아니라, 현재까지 찾은 LPS로 되돌아가는 명령이어야 하기 때문이다.
j라는 변수는 포인터의 역할을 하는 것이 아니라, 현재까지 찾은 Longest Prefix Suffix의 길이를 가리켜야하기 때문이다.
/* Instead */ j--
/* Use */ j = lps[j-1]
예시4: pat = "AABAAABBAABAAB"
0 1 2 3 4 5 6 7 8 9 10 11 12 13
pat | A A B A A A B B A A B A A B
lps | 0 1 0 1 2 2 3 0 1 2 3 4 5 ? (<- 3)
▲ ▲
j i (mismatch, j = lps[4] = 2)
▲ ▲
j i (match!)
j가 뒤로 가는 방법은 단순히 -1의 연산이 아니라, 이미 0..j에서 찾은 Prefix Suffix를 생략하는 것이다.
예시5: pat = "AABAAABBAABAAC"
위의 예시에서 마지막 문자만 바꾼 예시를 보자.
0 1 2 3 4 5 6 7 8 9 10 11 12 13
pat | A A B A A A B B A A B A A C
lps | 0 1 0 1 2 2 3 0 1 2 3 4 5 ? (<- 0)
▲ ▲
j i (mismatch)
▲ ▲
j i (mismatch)
▲ ▲
j i (mismatch)
잘 동작하는 것을 볼 수 있다.
LPS function
따라서 LPS를 만드는 함수는 이렇게 된다.
func genLPS(pat string) (lps []int) {
n := len(pat)
lps = make([]int, n)
i, j := 1, 0
for i < n {
if pat[i] == pat[j] {
j++
lps[i] = j
i++
} else {
if j == 0 {
lps[i] = 0
i++
} else {
j = lps[j-1]
}
}
}
return
}
KMP Algorithm
LSP의 개념을 이해했다면 KMP 알고리즘이 쉽다. txt, pat 각각에 인덱스 포인터 t, p를 초기화하고, 일치하는 경우와 아닌 경우를 나눠서 생각하면 된다.
0. 사용할 변수를 초기화한다.
T, P := len(txt), len(pat) // String lengths
t, p := 0, 0 // Index pointers
lps := genLPS(pat) // Longest Prefix Suffix array
pos := make([]int, 0) // Final answer
1. 두 문자가 같으면
t,p둘 다 전진한다.
if txt[t] == pat[p] {
t++; p++ // move pointers
}
2. 두 문자가 다르면
t는 정지한다.p는 suffix에 해당하는 prefix로 이동한다.- 단,
p == 0인 경우에는t는 전진한다.
if txt[t] != pat[p] {
if p == 0 {
t++ // move t
} else {
p = lps[p-1] // move p next to the prefix
}
}
3. 정답 조건
- 만약
p가 이동해서 패턴의 끝까지 도달하면 정답으로 표시하고p는 prefix로 이동한다.
if p == P {
pos = append(pos, t-p) // mark current position as answer
p = lps[p-1] // move p next to the prefix
}
4. 종료 조건
- 만약 더 확인해야하는 패턴의 문자보다 원문의 문자가 더 적으면 종료한다.
for {
...
if T-t <= P-p { // exit if there are more patterns than texts
break
}
}
KMP Algorithm
위의 조건들을 합쳐서 정리하면 다음과 같은 코드를 쓸 수 있다.
func kmp(txt, pat string) (pos []int) {
T, P := len(txt), len(pat) // String lengths
t, p := 0, 0 // Index pointers
lps := genLPS(pat) // Longest Prefix Suffix array
pos = make([]int, 0) // Final answer
for T-t <= P-p { // exit if there are more patterns than texts
if txt[t] != pat[p] { // mismatch
if p == 0 {
t++
} else {
p = lps[p-1] // move p next to the prefix
}
continue
}
t++; p++ // match
if p == P { // found
pos = append(pos, t-p) // mark current position as answer
p = lps[p-1] // move p next to the prefix
}
}
return
}