**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) 복잡도가 나옴

1. 조금 더 효율적으로 바꿀 수는 없을까?

2. 이미 알고 있는 정보를 활용하자!

   현재까지 검사한 문자열을 기준으로, 접두사와 접미사가 일치하는 부분에선 이어서 탐색 가능!

   (ABCAB라면, AB가 일치하므로, 문자열 검사 도중 MisMatch가 일어나면, AB or A로 이동해 탐색을 다시 진행 할 수 있음.

   뭐가 더 효율적일까? → 어차피 A로 이동하더라도, AB까지 일치할 걸 알고 있으니, 굳이 실제로 진행할 필요가 없는 A대신 가장 긴 AB로 이동하는 게 최적의 선택

   즉, 어떤 위치에서 MisMatch가 일어날 경우, 접두사 / 접미사가 일치하는 SubString중 가장 긴 상태로 전이 하면, 효율적으로 탐색을 이어서 진행 할 수 있음

   TargetString = “ABAABB”

   InputString = “ABAAABAABB”

   Input	A	B	A	A	A	B	A	A	B	B
   Target	A	B	A	A	B	B

용어 정리

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

1. 더 이상 매칭 되지 않는 경우, startIndex 를 ****굳이 **startIndex + 1**로 옮겨야 할까?

   현재 상태 **ABAA**에 대해서, 이동이 가능한 상태, 불가능한 상태는 어떤 경우일까?

   → 해당 상태의 접두사와 대응되는 현재 상태 **ABAA**의 동일한 길이의 접미사가

   일치하지 않는 경우!

   현재 위치한 인덱스를 **nowIndex**라고 할 때,

   3번 인덱스는 현재 **Fail(Miss-Match)**이 일어난 위치이므로, 고려하는 다음 위치

   nextIndex < 3 (nowIndex)

   ABAA의 접두사 목록

   접두사 (Prefix)	접미사 (Suffix)	이동 가능 여부
   A	A	Yes
   AB	AA	No
   ABA	BAA	No

   0번 인덱스가 **A**이므로, ****현재 상태 **ABAA**에서 ****이동이 가능 (ABAA의 접미사 A == A)

   1번 인덱스가 **AB**이므로, 현재 상태 ABAA 에서 이동이 불가능(ABAA의 접미사 AA != AB)

   2번 인덱스가 ABA 이므로, 현재 상태 ABAA 에서 이동이 불가능(ABAA의 접미사 BAA != AB)

   이렇게 현재 상태에서 이동 가능한 상태, 즉 접두사와 접미사가 일치하는 가장 긴 길이를,

   해당 상태의 Fail함수로 정의하고, **Fail(현재 상태) → 다음 상태**로 표현

   따라서, Fail(ABAA) → A

   이렇게, 모든 상태에 대해서 표현해보면,

   Status	Fail(Status)	Length
   A	Φ	0
   AB	Φ	0
   **A**B**A**	A	1
   **A**BA**A**	A	1
   **AB**A**AB**	AB	2
   ABAABB	Φ	0

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

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

Why ?

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