KMP 알고리즘

KMP 알고리즘 불일치가 일어난 직전까지 같았던 부분을 활용하여 검색을 진행하는 것입니다. 시간 복잡도는 O(N+M)이 됩니다

개요

접두부, 접미부

이 때, 절대 접두부나 접미부가 문자열의 전체가 될 수 없습니다.

위의 예제처럼 ABCA의 접두부를 기준으로 생각해 봅시다.

주어진 패턴을 보면 접두부 외에 패턴내에 ABCA가 있는 것을 알 수 있습니다. 이것을 활용하고자 하는 것이 KMP 알고리즘입니다.

이것의 실패 필터를 만들면 다음과 같습니다.

A	B	C	A	B	C	A	C
-1	-1	-1	0	1	2	3	-1

주어진 문자열에서 ABCABCAC가 있는지 찾는 KMP 방식은 다음과 같습니다.

문자열과 패턴을 0번째 인덱스부터 전부 비교합니다. 이 때, 실패 필터와 비교 했을 때 같다면, 나머지 인덱스를 넘기고 해당 인덱스부터 시작합니다.

KMP 알고리즘은 구현이 어려운 개념이니 대체 방안으로 cstring에 strchr(strstr)함수와 int strncmp함수를 사용할 수 있습니다.

사용법은 다음과 같습니다.

char str[] = “BlockDMask”;     char* ptr = strchr(str, ‘M’);  if(ptr != NULL) {         printf(“찾는 문자 : %c\n”, *ptr);        printf(“찾은 후 부터의 문자열 : %s”, ptr);      }	char str1[] = “BlockDMask”;  char str2[] = “BlockDMask”; strncmp(str1, str2, 5); //‘Block” 까지만 검사하므로 0 반환 strncmp(str1, str2, 6);  // D < F 이므로 음수 반환 strncmp(str2, str1, 6);  // F < D 이므로 양수 반환