KMP 알고리즘

안녕하세요, 전체 문자열에서 특정 패턴이 몇 번,어디서 등장하는지 효율적으로 알아낼 수 있는 KMP 알고리즘에 대해 포스팅하겠습니다. 포스팅하는 이유는 제가 요것 이해하는데 상당히 난황을 겪었고 (물론 지금도 100% 아는 것은 아니고 내일 과제 제출하는게 두렵습니다;) 그래서 복습해보고자 올리려고 합니다 !

Why KMP not 벨만포드 ?!

미션 ⛳️ : 전체 문자열에서 특정 패턴이 몇 번, 어디서 등장하는지 알아내기

ex. 전체 문자열 : p a n a m a b a n a n a / 패턴 : a n a

벨만포드를 쓸 경우 : a n a 가 window 가 되어서 문자열의 모든 인덱스를 돌게 됩니다.

그런데 여기서 2) ; 패턴 ana 가 문자열의 2번째 인덱스를 검사하는 경우를 살펴보면 굳이 a로 시작하지도 않은 문자열이 ana 인지 불필요한 검사를 하는 것을 알 수 있습니다. ana 는 a 로 시작해야하는데 n 으로 시작하는 문자열은 애초에 패턴이 되기엔 그른 녀석입니다. 문자열 모든 인덱스를 검사하다보면 이런 비효율적인 검사들이 늘어날 것입니다. 2),4) 등등의 검사는 그냥 없애도 되지 않을까 ? 진짜 필요한 검사만 해서 패턴을 찾자 -> KMP 알고리즘입니다

KMP 알고리즘

전체 문자열의 해당 인덱스를 인자로 하여 패턴의 문자열 몇 개까지 일치하는지를 나타내는 함수를 K(인덱스)=패턴의 문자 몇 개까지 일치하는지 로 정의하겠습니다.

ex. 전체 문자열 : p a n a m a b a n a n a / 패턴 : a n a

이면 패턴 문자 갯수는 총 3개인데 K(1)=3 이므로 1번 인덱스에서 해당 패턴이 등장함을 찾았습니다. 이처럼 K(x)=패턴의 총 문자 갯수가 되는 x 를 찾아주면 됩니다.

이를 구해주기 위해서 세 가지 변수를 알아야합니다.

• begin : 패턴이 몇 번째 인덱스를 검사하고 있는지

라고 할 수 있습니다.

• match : (순차적으로 필터링했을 때) 일치하는 갯수

이 때 주의할 점은 그냥 일치하는 갯수 (‘ama’ vs ‘ana’ -> 2개) 가 아니라

순차적으로 일치하는 갯수라는 점입니다. 즉 ‘ama’ vs ‘ana’ 인데 m에서 이미 n하고 일치하지 않으니 count 가 중단됩니다. match 는 1입니다.

• failure 함수 : f(x) ; 순차적으로 x번째 인덱스까지 슬라이싱된 문자열에서 접두사와 접미사가 일치하는 최대 길이 failure 함수 구하는 법은 더 뒤에 설명하겠습니닷

  p a n a m a b a n a n a 에서

  쓰려고 했는데 하 이거 예시가 좋은 예시가 아닌 것 같아서 잠시 바꾸겠습니다. 머쓱 ^^ ;

전체 문자열 : a b a b a a b c b a b / 패턴 : a b a b a c a

이라고 한다면 f(2) ; 맨 앞 시작 a 부터 2번 인덱스까지 슬라이싱하므로 ‘a b a’ 에서 접두사=접미사인 최장 문자열은 1(a)입니다.

f(5) ; 맨 앞 시작 a 부터 5번 인덱스까지 슬라이싱하므로 ‘a b a b a’ 에서 접두사 = 접미사인 최장 문자열은 3(aba) 입니다.

정의에 의해서, 패턴이 문자열의 모든 인덱스를 검사하면서 점점 일치되는 문자열 갯수가 늘어난다면 begin 은 그대로인데 m 은 증가하게 됩니다. 가령,

전체 문자열 : a b a b a a b c b a b / 패턴 : a b a b a c a 에서

a b a b a a b c b a b

a b a b a c a => begin=0,match=1

a b a b a a b c b a b

a b a b a c a => begin=0,match=2

…

a b a b a a b c b a b

a b a b a c a => begin=0,match=5

이런 식입니다. 딱 두 개만 더 일치하면 패턴의 문자 갯수 7개와 모두 일치해서 0번 인덱스에서부터 패턴을 발견한 것이 되지만 아쉽게도 문자가 다릅니다 ㅠ a != c

K(0)=5

이렇게 특정 인덱스에서 더 이상 일치되지 않은 경우 begin+m-f(m-1) 번 인덱스부터 다시 검사를 시작합니다. 즉 new begin=old begin+m-f(m-1) 이 되고 new match=f(m-1) 입니다. 다시 검사를 시작해줍니다.

예를 들어,

a b a b a a b c b a b

a b a b a c a => begin=0,match=5,K(0)=5

a !=c 이므로 더 이상 갱신이 못 되고 이러한 상황에 있다고 하였을 때,

new begin=0+5-f(4)=0+5-3=2

new match=f(4)=3 입니다.

즉,

1번째 인덱스는 b로 시작한 걸로 봐서 보나마나 패턴이 아니어서 뛰어넘고, 바로 2번째 인덱스 검사를 시작하는데 이 마저도 패턴의 앞 세 개 문자 ‘aba’까지 일치한다는 것은 직접 검사하지 않고 미리 유추해본 것입니다. 참 똑똑하죠 ? 👀 그니까 전체 패턴’ababaca’ 중에 aba 까지 일치하다는 것은 자동으로 파악하고 시작하니까 패턴의 남은 부분 ‘baca’와 문자열이 일치하는지만 검사하면 됩니다 !

이 과정이 패턴을 발견할 때까지 (k(x)=7 인 x 를 찾을 때까지) 반복됩니다.

갱신 과정 설명

문자 불일치가 발생할 경우 왜

new begin=old begin+m-f(m-1) 이 되고 new match=f(m-1) 으로 갱신되는지 설명하겠습니다.

a b a b a a b c b a b

a b a b a c a => begin=0,match=5,K(0)=5

의 상황에서 불일치가 발생하여서 K(0)=5로 결론지어졌습니다.

begin=0,match=5,K(0)=5 라는 말은 다시 말하면 a b a b a … 에서 a b a b a 5개까진 패턴과 일치한다는 말입니다. 이 때 f(5)=3 (prefix&suffix=’aba’) 이므로, a b a b a 중 [0,1,2] 번 인덱스(prefix ‘aba’) 까지도 당연히 패턴이 일치합니다. = 패턴 맨 앞 세 글자는 a b a 입니다.

그런데 failure 함수의 특성 상 [0,1,2] 번 인덱스(prefix ‘aba’) = [2,3,4] 번 인덱스(suffix ‘aba’) 입니다.

정리하자면 패턴 맨 앞 세 글자가 a b a 이고 [2,3,4] 번 인덱스인 suffix 도 a b a 이기 때문에 2번 인덱스에서 출발하여 2,3,4 까지의 패턴은 이미 일치한 것으로 자동적으로 유추하고 남은 부분만 검사할 수 있는 것입니다 ! (= ‘[2,3,4~] 에서 패턴 남은 부분 검사를 시작하면 이번엔 패턴과 100% 일치할지도?’) 입니다

• ‘1번 인덱스인 b를 건너뛰고 2번 인덱스인 a부터 검사를 시작할꺼야’ : new begin=old begin+m-f(m-1)

  자세히 살펴보면 old begin 에 m-f(m-1) 을 더해줌으로써 suffix이자 새로운 검사에서의 prefix후보를 new begin 으로 갱신한 것입니다 !

  m-f(m-1) : 전체 패턴과 일치하는 문자 갯수 - 맨 앞부터 시작해서 prefix가 끝나는 부분 = 새로운 suffix가 시작될 수 있는 부분 => suffix 가 시작되는 해당 m 내의 인덱스

  ex. a b a b a 에서 m-f(m-1)=5-3=2

  old begin + m-f(m-1) : 전체 패턴에서 suffix가 시작되는 인덱스

• ‘2번 인덱스부터 쭉 검사하는데 이미 2~4번 인덱스까지는 패턴과 일치함을 파악했어. 남은 5~7번 인덱스만 확인하자’ : new match=f(m-1)

• f(m) 이 아니라 f(m-1)인 이유는 인덱스는 0번째부터 시작하기 때문입니닷 ex. ‘ababa’까지의 failure 함수는 f(5)가 아니라 f(4)입니다

  failure 함수 구하는 방법

문자열 ‘a b a b a b’ 의 failure 함수를 구한다고 하면 쌍둥이 B를 만들어줍니다.

문자열 A = ‘a b a b a b’

​ B = ‘a b a b a b’

이제 B가 A의 인덱스를 순차적으로 돌며 아까와 동일한 방식으로 begin 과 match 를 카운팅해줄 것입니다. 이 때 f(begin+match-1)=match 가 됩니다. 해당 이유에 대해서도 설명하겠습니다.

그리고 default 로 f(0) =0 (0번째 인덱스까지이므로 문자열 딱 1개 ->prefix,suffix가 존재할 수 없음) f(1)부터 구해주면 됩니다

맨 처음부터 어긋났으므로 검사를 건너뛸 수 없습니다.

바로 다음 인덱스 검사를 시작합니다.

A 문자열이 끝났으므로 검사를 더 진행할 수 없습니다. 끝냅니다.

Why f(begin+match-1)=match ?

즉 match 가 1이라는 말은 ‘a b a’ (A) 의 suffix 1개 (a)가

’ a b a ~’ (B) 의 prefix 1개 (a) 랑 같다는 말입니다. 이 때 A,B는 쌍둥이입니다. (A=B) 따라서 전체 문자열의 부분 문자열인 ‘aba ‘ 는 시작도 a 로 하고 끝나는 것도 a 로 끝난다는 것을 알 수 있습니다. 따라서 f(2)=1 이 됩니다.

f(x) 의 x가 몇번째 인덱스까지인지를 한정해놓는 역할을 한다고 할 때

f(2) 에서 2는 ‘aba’ 까지 즉 2번째 인덱스까지 중에서만 고려할꺼야 이렇게 한정해놓는 역할을 합니다

즉 x 자리엔 몇번째 인덱스까지를 살펴볼지 그 한정선이 정확하게 들어가야 합니다.

이 때 begin=2이고 match=1 (‘a’) 이므로 2+1을 하게 되면 한정선 갱신을 한번 중복으로 해줘서 ‘aba’ 까지 즉 2번째 인덱스까지 중에서만 고려할꺼야 인데 이것이 f(2)가 아닌 f(3) 으로 잘못 표기됩니다. 따라서 -1을 해줘서 한정선 갱신을 두번 해준 것을 제외해야합니다.

A=B이므로 f(begin+matach) 는 A와 B의 동일 문자 (a)에 칸막이가 각각 한 번씩 쳐졌다는 것은 결국

마찬가지로

에서 match가 2라는 말은 ‘a b a b’ (A)의 suffix 2개 (ab) 가 ‘a b a ~’ (B) 의 prefix 2개 (ab) 와 같다는 말입니다. A=B이므로 전체 문자열의 부분 문자열인 ‘abab’ 는 시작도 ab 로 하고 끝나는 것도 ab 로 끝난다는 것을 알 수 있습니다. 따라서 f(3)=2 가 됩니다.

이 때 begin=2 이고 match=2 (‘ab’) 이므로 2+2를 하게 되면 한정선 갱신을 한번 중복으로 해줘서 ‘abab’ 까지 즉 3번째 인덱스까지 중에서만 고려할꺼야 인데 이것이 f(3)이 아닌 f(4) 으로 잘못 표기됩니다. 따라서 -1을 해줘서 한정선 갱신을 두번 해준 것을 제외해야합니다.

A=B이므로 A와 B의 동일 문자 (a)에 칸막이가 각각 한 번씩 쳐졌다는 것은 결국