KMP 알고리즘 / 백준 5525 IOIOI

기본 소개

문자열 S 내 특정 패턴A에 해당하는 문자열을 찾을 때, 패턴A 내의 접두사, 접미사를 활용하여 패턴 내 모든 문자를 다 비교하지 않고 넘어가서 비교 횟수를 줄이는 알고리즘 이다.

---

브루트 포스와 의 비교 

브루트 포스

O<NK>의 시간 복잡도를 지닌다. 문자열 비교를 할 때 아래와 같이 한칸씩 밀어 확인하면서 모든 문자열이 맞아들어가는지 같이 보기 때문이다.

 

KMP

O<N+K>의 시간복잡도를 지닌다. 문자열 비교시 원래 문자열인 S를 하나씩 지나가는건 맞지만, 아무때나(?) 패턴매칭을 시도하는 부루트 포스와는 달리, 원문과 패턴에 각각 포인터를 지니고, 1대1 로만 비교 하고 포인터 관리에 있어 중복된 구간을 막는다.

이 때 포인터 관리를 위해서, 특정 구간까지의 접두사와 접미사가 어디까지 일치하는지를 가지는 테이블을 사용한다.

 

---

LCS

위에 언급한 패턴 내 특정 구간까지의 문자열이, 접두사와 접미사가 어디까지 일치하는지를 가지는 테이블이다.

이를 이용하면, 패턴비교시에 패턴 비교용 포인터를 어디까지 점프가 가능한지 알아낼 수 있다.

이는 아래와 같은 규칙으로 만들 수 있다.

 

패턴: ABCDABD

문자	A	B	C	D	A	B	D
값 Row 2, Col 1	j 0	i 0 [불일치]
	j 0 [이동됨]	i 0 [불일치]
	j 0	0	i 0 [불일치]
	j 0 [이동됨]	0	i 0 [불일치]
	j 0	0	0	i 0 [불일치]
	j 0 [이동됨]	0	0	i 0 [불일치]
	j 0	0	0	0	i = j + 1 = 1[일치]
	0	j 0 [이동됨]	0	0	1	i [이동됨] i = j + 1 = 2
	0	0	j 0	0	1	2	i  0 [불일치]
	j 0 [이동됨]
결과배열[L]	0	0	0	0	1	2	0

• i = 1, j = 0 위치에 놓는다.
• i 를 증가하는 도중 j를 상황에 맞게 위치를 옮긴다.
  -> j 번째 문자와, i 번째 문자가 똑같으면 j 위치 증가 후 그 위치 값을 결과배열 L 의 i 에 넣는다.
  -> j 번째 문자가, i 번째 문자가 다르면, j 위치를 결과배열 L[j-1] 값으로 옮긴 후 비교를 수행 후 다음 단계(i 증가)로 넘어간다.

구현코드

S = 'ABABCDABD'
P = 'ABCDABD'

def makeLPS(pattern):
    j = 0
    ln = len(pattern)
    LPS = [0 for _ in range(ln)]
    for i in range(1,ln):
        while j > 0 and pattern[j] != pattern[i]:
            j = LPS[j - 1]
        if(pattern[j] == pattern[i]):
            j += 1
            LPS[i] = j
    return LPS

LPS = makeLPS(P)

---

KMP 알고리즘 구현

위에 구한 LCS 배열을 L 이라 하고, 원본 문자열을 S 패턴 문자열을 P 라고 하자.

또한, 원본 문자열의 포인터를 i 라 하고, 패턴 문자열의 포인터를 j 라고 하자.

 

원본	A <i>	B	A	B	C	D	A	B	D
패턴	A <j>	B	C	D	A	B	D

원본	A	B <i>	A	B	C	D	A	B	D
패턴	A	B <j>	C	D	A	B	D

 

일치할 때에는 둘 다 위치를 증가시켜 준다.

원본	A	B	A <i>	B	C	D	A	B	D
패턴	A	B	C <j>	D	A	B	D

 

불일치 발생 시, j 포인터를 이동해 주는데, 이 때 L배열을 이동해서 다음 탐색시에 j 포인터를 어디서부터 잡아야 할지 결정해준다.

L 배열의 의미는 패턴 내 현재 길이까지 어디가 접두사 하고 접미사가 겹치는 문자열인가 판독하기 위해 쓰인다.

패턴 내 이전 문자까지를 기준으로 잡고 새로 판독하도록 포인터 변경. 여기서는 L[2 - 1] 인 0으로 이동 후 재비교 한다.

 

이미 기존 원본과 비교한 i 까지의 접미사 구간하고, 다음에(?) 판독할 패턴 내 접두사 구간이 겹치기 때문에 중복을 제거하는 것 이다.

예시를 잘 들었어야 했는데, 지금의 경우 마치 초기화 된것처럼 보이지만... 접두사 구간을 찾아서 다음 포인터를 지정하는게 맞다.

원본	A	B	A <i>	B	C	D	A	B	D
패턴	A <j>	B	C	D	A	B	D

원본	A	B	A	B <i>	C	D	A	B	D
패턴	A	B <j>	C	D	A	B	D

 

계속 일치하므로 최종적으로 아래와 같이 i와 j 같이 증가

원본	A	B	A	B	C	D	A	B	D <i>
패턴	A	B	C	D	A	B	D <j>

 

j 포인터가 패턴 길이와 동일할 경우 실제 패턴 매칭이 끝난다는 것을 의미하므로 해당 구간을 저장하고, 다음 탐색을 위해서 j를 접두사와 접미사가 일치하는 최대 위치로 다시 옮겨놓는다. j = L[j]

 

원문: [접두]----[접미] ******

패턴: [접두]@---[접미] 일 경우

다음번 탐색할 구간일 때 처음부터 비교하는게 아니라 [접두]와 [접미]가 같으므로 j 포인터를 @ 위치로 스킵하도록 미리 처리해 두는 것이다.

 

구현코드

def KMP(S,P,L):
    j = 0
    ln = len(P)
    for i in range(0,len(S)):
        while j > 0 and P[j] != S[i]:
            j = L[j - 1] # 마지막으로 패턴 내 일치했던 부분까지 이동
        if(P[j] == S[i]):
            if(j == ln - 1):
                print('발견했습니다!', S[i-ln+1:i+1])
                j = L[j]
            else:
                j += 1
KMP(S,P,LPS)

 

---

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

 

백준 5525번 문제

이 문제는 브루트포스로 풀게 되면 시간 초과로 인해 서브태스크2를 통과할 수가 없다.

따라서 시간복잡도를 줄여야하는데, 나는 KMP를 사용하여 해당 문제를 풀었다.

 

import sys
input = sys.stdin.readline
N = int(input().rstrip())
M = int(input().rstrip())
S = input().rstrip()
size = 3 + 2 * (N - 1)
P = ''.join(['I' if i % 2 == 0 else 'O' for i in range(size)])
def makeLPS(pattern):
    j = 0
    ln = len(pattern)
    LPS = [0 for _ in range(ln)]
    for i in range(1,ln):
        while j > 0 and pattern[j] != pattern[i]:
            j = LPS[j - 1]
        if(pattern[j] == pattern[i]):
            j += 1
            LPS[i] = j
    return LPS

LPS = makeLPS(P)

def KMP(S,P,L):
    cnt = 0
    j = 0
    ln = len(P)
    for i in range(0,len(S)):
        while j > 0 and P[j] != S[i]:
            j = L[j - 1] # 마지막으로 패턴 내 일치했던 부분까지 이동
        if(P[j] == S[i]):
            if(j == ln - 1):
                cnt += 1
                j = L[j]
            else:
                j += 1
    return cnt
print(KMP(S,P,LPS))