KMP 알고리즘

KMP 알고리즘

 

정의

KMP(커누스 모리스 프랫 3명의 사람이 같이 만들어서 KMP)알고리즘이며 
불필요한 비교 즉, 어차피 틀릴걸 아는 부분은 건너뛰어버리는 원리를 이용하는 대표적인 문자열 매칭 알고리즘이다.
문자열 매칭이란 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾아내는 것을 의미한다.

쉽게 말하면 우리가 브라우저에서 ctrl+f를 통해 찾고자하는 문자열을 검색하는 행위라고 생각하면 된다.

 

과정

1. 패턴 내 접두사 , 접미사를 활용하자.

kmp 알고리즘의 핵심은 패턴의 접두사와 접미사 개념을 적극 활용하여 '반복되는 연산을 얼만큼 건너뛸 수 있는 지'에 대해
집중한다는 것이다.

 

패턴 내에 존재하는 접두사와 접미사가 '일치' 한다면 접미사를 접두사로 다시 바라봄으로써 문자열 탐색을 이어서 진행할 수 있기 때문이다.

 

2.  동일 접두사 - 접미사 전처리 테이블을 만들자 = lps 배열을 만들자

 

3.  KMP 함수를  만들자

위에서 만든 lps 배열을 끝가지 탐색하며 패턴이 몇번 나타나는 지 알아보자. 

---

LPS  

Longest Prefix Suffix의 약자로 접두사와 접미사가 같은 구간의 길이가 긴 부분을 찾는 과정이다.

 

여기서 핵심은 두개의 포인터와 lps 배열이다. 

 

let arr = Array(S)
let n = arr.count

if n <= 1 { // 문자열 길이가 1보다 작거나 같으면
// s보다 짧은 prefix, suffix 존재 x
    return 0
}

// lps[i] = i까지 접두사와 접미사가 가장 긴 일치하는 문자열 길이
var lps: [Int] = [Int](repeating: 0, count: n)
var len: Int = 0  // 이전에 가장 긴 prefix suffix의 길이 = prefix 끝나는 문자 다음의 인덱스 포인터
var pos: Int = 1 // 현재 문자 가르키는 포인터

 

• arr[len] == arr[pos] 
  • lps[len] = len + 1로 연장
  • 이후 len과 pos를 모두 한칸씩 이동 
• arr[len] != arr[pos]
  • 이전 lps값인 lps[len-1] 이  0이 아닌지 결정한다.
    • lps[len-1] == 0 이라면, 이전에 일치한 접두사 - 접미사가 없다는 의미이므로 len = 0으로 설정하고 pos는 다음으로
    • len[len-1] !=  0 이라면, 이전에 일치한 접두사 - 접미사가 있다는 의미이므로 이전 lps값을 기준으로 검사한다.

TEXT	pos	len	lps	설명
ABCAAABC	1	0	[0,?,?,?,?,?,?,?]	arr[len] != arr[pos]  len이 0이므로  lps[pos] = 0 pos 증가
ABCAAABC	2	0	[0,0,?,?,?,?,?,?]	arr[len] != arr[pos]  len이 0이므로  lps[pos] = 0 pos 증가
ABCAAABC	3	0	[0,0,0,?,?,?,?,?]	arr[len] == arr[pos]  lps[len] = len+1 len 증가 pos 증가
ABCAAABC	4	1	[0,0,0,1,?,?,?,?]	arr[len] !=arr[pos]  len이 0이 아니므로  len = lps[len-1] = 0 pos 그대로
ABCAAABC	4	0	[0,0,0,1,?,?,?,?]	arr[len]==arr[pos]  lps[len] = len+1 len 증가 pos 증가
ABCAAABC	5	1	[0,0,0,1,1,?,?,?]	arr[len] !=arr[pos]  len이 0이 아니므로  len = lps[len-1] = 0 pos 그대로
ABCAAABC	5	0	[0,0,0,1,1,?,?,?]	arr[len] == arr[pos]  lps[len] = len+1 len 증가 pos 증가
ABCAAABC	6	1	[0,0,0,1,1,1,?,?]	arr[len] == arr[pos]  lps[len] = len+1 len 증가 pos 증가
ABCAAABC	7	2	[0,0,0,1,1,1,2,?]	arr[len] == arr[pos]  lps[len] = len+1 len 증가 pos 증가
[0,0,0,1,1,1,2,3]

 

코드

import Foundation

func computeLPS(_ pattern: [Character]) -> [Int] {

    let n = pattern.count
    
    var lps: [Int] = [Int](repeating: 0, count: n)
    
    var len = 0
    var pos = 1
    
    while pos < n {
        
        if pattern[len] == pattern[pos] {
            lps[pos] = len + 1
            pos += 1
            len += 1
            
        } else {
            
            if len == 0 {
                pos += 1
            
            } else {
                len = lps[len-1]
            }
            
        }
        
        
    }
    
    return lps
}

---

KMP 진행 

앞서 lps 배열을 구했으므로 kmp 알고리즘은 lps값을 이용해서 불필요한 검사를 건너뛴다.

 

예를 들어보자. 

 

문자열 s = ABCDABCDABE 이고, 찾고 싶은 패턴이 ABCDABE 라고 했을 때 , 위에서 만든 lps 이용해서 빠르게 찾아보자.

 

출처 https://woo-niverse.tistory.com/230#3.%20KMP%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

여기서 i와 j가 5번까지는 모두 일치하여 두 포인터 모두 증가한다.

 

이후 i = 6 , j = 6 , s[i] = C , pattern[j] = E , s[i] != pattern[j] 이므로 틀리다. 

 

이때 우리는 j-1의 lps의 lps[j-1]인 2인걸 해석해보면 앞에 AB는 prefix와 suffix가 겹치는 부분이므로 앞의
prefix를 뒤의 suffix부분으로 옮기면 불필요한 연산을 건너 뛸 수 있다. 

 

즉 , 앞의 2칸은 일치하는 값이므로 j 인덱스를 3번째(2)로 옮긴다.

 

https://woo-niverse.tistory.com/230#3.%20KMP%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

그림으로 보면 마치 이렇게 말이다. 이번에 코드로 한번 봐보자.

 

코드

import Foundation

func computeLPS(_ pattern: [Character]) -> [Int] {

    let n = pattern.count
    
    var lps: [Int] = [Int](repeating: 0, count: n)
    
    var len = 0
    var pos = 1
    
    while pos < n {
        
        if pattern[len] == pattern[pos] {
            lps[pos] = len + 1
            pos += 1
            len += 1
            
        } else {
            
            if len == 0 {
                pos += 1
            
            } else {
                len = lps[len-1]
            }
            
        }
        
        
    }
    
    return lps
}


func kmpSearch(_ s: [Character], _ pattern: [Character]) -> [Int] {
    
    let n = s.count
    let m = pattern.count
    
    let lps = computeLPS(pattern)
    
    var matchedStartIndex: [Int] = []
    
    var i: Int = 0
    var j: Int = 0
    
    
    while i < n {
        
        if s[i] == pattern[j] {
            i += 1
            j += 1
        } else {
            if j == 0 {
                i += 1
            } else {
                j = lps[j-1]
            }
            
        }
        
        if j == m {
            matchedStartIndex.append(i-j) // 패턴 찾은 인덱스 시작위치 
            j = lps[j-1]
        }
        
    }
    
    return matchedStartIndex
}

let s = Array(readLine()!)
let pattern = Array(readLine()!)

let answer = kmpSearch(s, pattern)
print(answer.count)
answer.forEach{
    print($0+1)
}

 

 

시간 복잡도

O(M+N) =  lps 계산 M + kmpSearch N

---

관련문제

https://www.acmicpc.net/problem/1786

 

---

참고

 

KMP 알고리즘 (문자열 매칭)

 

문자열 검색 : LPS와 KMP 알고리즘