알고리즘 공부

KMP

까진호두 2022. 8. 24. 16:43

문자열 패턴매칭 알고리즘인 KMP 알고리즘입니다.

아호코라식 공부한지 꽤 시간이 지났는데, 그동안 KMP는 정리하지 않다가 이제야 글을 쓰네요 ㅎㅎ

노션에 정리한 글을 붙여넣은거라, 내용이 조금 깨져있어서 보기 힘드실 수 있습니다.

노션 링크를 참고해주세요!

https://hollow-cushion-33f.notion.site/KMP-04882b3843c84c099eb343ab683a9b0b

KMP

Knuth-Morris-Pratt Algorithm

Naive한 문자열 매칭의 시간 복잡도?

패턴 문자열의 길이를 M, 주어진 문자열의 길이를 N이라고 할 때,

**시간복잡도 : O(NM)**

inputString = "aaaaaa"
targetString = "aa"
matchList = []

for i in range(len(inputString) - len(targetString)):
	flg = True
	for j in range(len(targetString):
		if inputString[i + j] != targetString[j]:
			flg = False
			break

	if flg:
		matchList.append(i) #시작 위치 넣어주기!
		
		
#InputString의 각 위치마다 최대 M번만큼 반복될 수 있으므로, O(N * M) 복잡도가 나옴

조금 더 효율적으로 바꿀 수는 없을까?
이미 알고 있는 정보를 활용하자!(ABCAB라면, AB가 일치하므로, 문자열 검사 도중 MisMatch가 일어나면, AB or A로 이동해 탐색을 다시 진행 할 수 있음.즉, 어떤 위치에서 MisMatch가 일어날 경우, 접두사 / 접미사가 일치하는 SubString중 가장 긴 상태로 전이 하면, 효율적으로 탐색을 이어서 진행 할 수 있음InputString = “ABAAABAABB”Input A B A A A B A A B B

Target A B A A B B
TargetString = “ABAABB”
뭐가 더 효율적일까? → 어차피 A로 이동하더라도, AB까지 일치할 걸 알고 있으니, 굳이 실제로 진행할 필요가 없는 A대신 가장 긴 AB로 이동하는 게 최적의 선택
현재까지 검사한 문자열을 기준으로, 접두사와 접미사가 일치하는 부분에선 이어서 탐색 가능!

용어 정리

startIndex 각 문자열 매칭과정에서, 문자열을 비교할 첫 위치를 나타내는 인덱스

nowIndex	현재 상태를 나타내는 인덱스
Fail(x) → y	x상태에서 Fail(MisMatch)가 일어났을 때 이동할 상태

현재 상태까지의 문자열에서, 접두사 / 접미사가 일치하는 최대의 길이를 나타냄 |

더 이상 매칭 되지 않는 경우, startIndex 를 ****굳이 **startIndex + 1**로 옮겨야 할까?→ 해당 상태의 접두사와 대응되는 현재 상태 **ABAA**의 동일한 길이의 접미사가현재 위치한 인덱스를 **nowIndex**라고 할 때,nextIndex < 3 (nowIndex)접두사 (Prefix) 접미사 (Suffix) 이동 가능 여부

A A Yes

AB AA No

ABA BAA No

0번 인덱스가 **A**이므로, ****현재 상태 **ABAA**에서 ****이동이 가능 (ABAA의 접미사 A == A)2번 인덱스가 **ABA** 이므로, 현재 상태 **ABAA** 에서 이동이 불가능(ABAA의 접미사 BAA != AB)해당 상태의 Fail함수로 정의하고, **Fail(현재 상태) → 다음 상태**로 표현이렇게, 모든 상태에 대해서 표현해보면,Status Fail(Status) Length

A Φ 0

AB Φ 0

ABA A 1

ABAA A 1

ABAAB AB 2

ABAABB Φ 0
따라서, Fail(ABAA) → A
이렇게 현재 상태에서 이동 가능한 상태, 즉 접두사와 접미사가 일치하는 가장 긴 길이를,
1번 인덱스가 **AB**이므로, 현재 상태 **ABAA** 에서 이동이 불가능(ABAA의 접미사 AA != AB)
ABAA의 접두사 목록
3번 인덱스는 현재 **Fail(Miss-Match)**이 일어난 위치이므로, 고려하는 다음 위치
일치하지 않는 경우!
현재 상태 **ABAA**에 대해서, 이동이 가능한 상태, 불가능한 상태는 어떤 경우일까?

모든 상태에 대해서 이렇게 Prefix Suffix를 구하는 건 매우 비효율적임! (O(M^2))

하지만, 이전 문자열들의 Fail(prev) 들을 통해 현재 문자열의 Fail(now)을 빠르게 구할 수 있음

Why ?

**~** → 임의의 문자열 (Fail(~) → Φ)

**X**→ 임의의 문자열

**Y** → 새로 추가된 문자

Z → Y가 아닌 문자

기존 문자열 OriginString을 X~X로 표현될 때, Fail(OriginString) = X

길이가 1 추가된 다음 상태 NextString를 X~XY로 표현할 수 있음.

이 때, ~의 맨 첫 글자에 따라,

만약 ~의 맨 첫 글자가 Y라면
NextString은 다시 XY~'XY → X'~X'로 표현 가능 → Fail(NextString) = X'(Len(X) + 1)

그렇지 않다면,Fail(OriginalString) = X에서 Y를 이용해 전이 할 수 없음.Y를 덧붙일 수 있는 최장 길이의 SubString로 이동하게 됨

#Prefix / Suffix가 일치하는 최대 길이까지 Fail()을 타고 이동함
	while Fail(OriginalStr) != Φ and targetStr[len(Fail(OrignialStr))] != X:
		OriginalStr = Fail(OriginalStr)

#만약 Fail의 결과 위치에서 다음 위치로 전이가 가능하다면, +1이 더해짐	(그렇지 않다면 Root(0))
Fail(NextStr) = OriginalStr + (targetStr[len(OriginalStr)] == X)

위의 로직은, 아래의 코드로 일반화 할 수 있음
즉, Fail(NextString) = Recursion(Fail(OrignialString))즉, Prefix / Suffix가 일치하는,
NextString은 X~XY로 표현되고,

결과적으로, 위와 같은 방식으로 Fail을 구하는 경우 최대 M번의 상태 전이 + M번의 Fail 이동이 가능하므로, O(2M) = O(M)으로 나타낼 수 있음.

**Query**처리

위에서 구해진 Fail()을 바탕으로, 패턴 문자열과 위치하는 SubString의 존재 유무와 위치 등을 빠르게 구할 수 있음.

전체 문자열의 길이 N번만큼의 전이가 일어나고, 그에 따라 최대 N번의 Fail함수를 통한 상태 전이가 가능하므로, Time Complexity는 O(2N) = O(N)으로 나타낼 수 있음

Time Complexity

Fail Func Construction O(M)

Query	O(N)
Total	O(N + M)

Example

TargetString = ABABAB

Automata 표현

Target A B A B A B

Fail

InputString이 ABABBABABAB인 경우

Input Stat Flow

A	1	0 → 1
B	2	1 → 2
A	3	2 → 3
B	4	3 → 4
B	0	4 → 2 -> 0
A	1	0 → 1
B	2	1 → 2
A	3	2 → 3
B	4	3 → 4
A	5	4 → 5
B	6(Accept)	5 → 6
A	5	6 → 4 -> 5
B	6(Accept)	5 → 6

AcceptedIndex= [10,12]

728x90

저작자표시

A	A	Yes
AB	AA	No
ABA	BAA	No

A	Φ	0
AB	Φ	0
ABA	A	1
ABAA	A	1
ABAAB	AB	2
ABAABB	Φ	0