KMP 검색 알고리즘

KMP 검색 알고리즘이란?

문자열 안에서 부분 문자열을 검색할 때,

검색에 실패한 위치를 기반으로 비교할 필요가 없는 문자열은 건너뛰고, 다음 번 검색 위치를 결정하는 알고리즘.

 

- 찾고자 하는 문자열이 중복되지 않을 경우

예를 들어 다음과 같은 데이터에서 'MYBK' 처럼 중복되지 않는 문자열을 찾을 경우.

M

Y

B

B

A

G

M

Y

B

K

'MYB'까지는 일치하지만 4번째 K가 일치하지 않는다.

이럴 경우 'MYB' 다음 위치부터 검색을 다시 시작한다.

 

- 찾고자 하는 문자열이 중복되는 경우

예를 들어 다음과 같은 데이터에서 'MBMBC' 처럼 중복되는 문자열을 찾을 경우.

M

B

M

B

M

B

C

K

A

B

M

B

M

C

M

B

A

B

C

A

'MBMB' 까지는 일치하지만 5번째 C가 일치하지 않는다.

이럴 경우 'MB' 다음 위치부터 검색을 다시 시작한다.