[개념] KMP 알고리즘

 

KMP 알고리즘은 문자열 A와 문자열 B가 있을 때, 문자열 A에서 문자열 B를 찾아주는 알고리즘 입니다.

KMP는 KMP를 만든 사람의 이름인 Knuth, Morris, Prett 세 사람의 앞 글자를 따서 KMP 알고리즘이라고 불립니다.

 

 

1) 모든 경우를 다 탐색할 경우

문자열 A의 길이가 N,문자열 B의 길이가 M이라면 O(N*M)의 시간 복잡도를 가지게 됩니다.

만약 N,M이 10만인 문제가 주어진다면 시간 초과를 보게 됩니다.

 

2) KMP 알고리즘을 사용할 경우

놀랍게도 O(N+M)의 시간복잡도만에 문자열 A에서 문자열 B를 검색 할 수 있습니다.

 

그러면 AKAKA라는 문자의 pi[4]는 1일까요?

아닙니다 절반을 넘는경우도 세줍니다.

AKA==AKA이기 때문에 pi[4]는 3이되겠군요.

 

failure function의 위치가 KMP 알고리즘의 핵심이라고 불 수 있습니다

 

 

참고 블로그

https://bowbowbow.tistory.com/6

https://jason9319.tistory.com/130