고전 문자열 매칭 알고리즘 (KMP) 해석

no_mkd

일.문제 재서술

문자열 S1 이 있고, S1 에서 문자열 S2 와 완전히 일치하는 부분을 구합니다. 예를 들어: S1 = "ababaababc", S2 = "ababc"

매칭 결과는 5 입니다 (S1 중"ababc"의 a 위치). 물론 S1 중에 여러 개의 S2 가 있어도 관계없습니다. 첫 번째를 찾을 수 있으면 두 번째도 찾을 수 있습니다..

가장 쉽게 생각나는 방법은 이중 루프로 비트별로 비교하는 것입니다 (BF 알고리즘). 하지만 최악의 경우 BF 알고리즘의 시간 복잡도는 m * n 에 달하며, 이는 실제 응용에서 받아들일 수 없습니다. 그래서 3 명이 KMP 알고리즘을 생각해냈습니다 (KMP 는 3 명의 이름입니다..)

이.KMP 알고리즘 구체적 과정

(먼저 KMP 알고리즘의 공식 정의를 보려고 하지 마십시오. 매우 이해하기 어렵기 때문에 여기서는 정의를 제시하지 않습니다..)

S2 = "ababc"를 주의 깊게 관찰하십시오. 중요한 점은: 시작 부분에 ab 가 나타나고, 중간 부분에도 ab 가 나타난다는 것입니다 (이 세부사항을 기억해 두십시오)

어떤 순간을 가정합니다:

이때 abab 부분 매칭이 성공하고, S1 의 위치 포인터는 a 를 가리키며, 현재 하고 있는 일은 a 와 c 를 비교하는 것이며, 결과는 매칭 실패입니다

BF 알고리즘이라면, 다음 단계는 S1 의 위치 포인터를 두 번째 b 로 백트래킹하고, S2 의 위치 포인터를 시작 부분의 a 로 리셋한 후, b 와 a 를 비교하고, 그 후..
KMP 알고리즘이라면, 다음 단계는 S1 위치 포인터를 변경하지 않고 (a 를 가리킨 채), 점프 테이블 (next 테이블) 을 조회하여 점프 값 2 를 얻고, S2 의 포인터를 두 번째 a 로 이동한 후, a 와 a 를 비교하고, 그 후..

KMP 단계가 이해되지 않아도 관계없습니다. 점프 테이블 (next 테이블) 이 무엇인지 아직 설명하지 않았으므로. 여기서는 결과만关注하면 됩니다:

BF 알고리즘에서는 S1 의 포인터가 왼쪽으로 이동했습니다 (백트래킹)
KMP 알고리즘에서는 S1 의 포인터가 뒤로 가지 않았습니다 (백트래킹 없음)

KMP 알고리즘에는 백트래킹 과정이 존재하지 않으므로 많은 시간을 절약합니다 (S1 의 포인터는 처음부터 끝까지 한 번만 걸으면 됩니다)

KMP 알고리즘의 핵심인 점프를 다시 살펴봅시다

왜 점프할 수 있는가? S2 = "ababc"를 주의 깊게 관찰하십시오. 이 문자열의 특징은: 시작 부분에 ab 가 나타나고, 중간 부분에도 ab 가 나타난다는 것입니다 (이 세부사항을 기억하십니까). 자세히 설명합니다:

S2末尾의 c 가 S1 의 제 k 위와 매칭에 실패하면, 두 가지 정보를 추론할 수 있습니다:

이번 매칭이 실패했습니다 (c 의 매칭 실패는 S1 중의 어떤 부분이 S2 와 매칭되지 않음을 의미합니다)
S1 중 제 k 위 앞의 4 위는 반드시 abab 입니다 (S2 중의 abab 과 S1 중의 어떤 부분의 매칭이 성공한 후에야 S2 의 c 와 S1 제 k 위의 비교가 발생할 수 있습니다)

제 2 점을 무시하면, 다음 단계는 S1 포인터의 백트래킹, 즉 BF 알고리즘이 할 일입니다. 제 2 점을 잡고,再加上 S2 문자열의 특징:

시작 부분에 ab 가 나타나고, 중간 부분에도 ab 가 나타난다는 것 (다시 한 번 강조합니다)

를 고려하면 KMP 알고리즘을 얻을 수 있습니다 (S1 중 제 k 위 앞의 ab 가 S2 시작 부분의 ab 와 매칭되었으므로, S1 의 제 k 위와 S2 의 제 3 위 a 비교로 직접 점프할 수 있습니다)

조금 이해된 것 같습니다. 그렇다면 이 점프 값 2 는 어떻게 얻는가? 더 많은 예를 듭니다:

S2 = "aba" 마지막 위의 점프 값은 0
S2 = "abaa" 마지막 위의 점프 값은 1
S2 = "abcabc" 마지막 위의 점프 값은 2

무엇인가 발견했습니까? 맞습니다. S2 중 제 x 위 (여기서의 x 는 0 부터 셈) 의 점프 값을 구하는 과정은 다음과 같습니다:

x = 0 이면, S2[x] 의 점프 값은 -1 (첫 번째 요소의 점프 값은 -1)
x = 1 이면, S2[x] 의 점프 값은 0 (두 번째 요소의 점프 값은 0)
S2[x - 1] = S2[0] 이면, S2[x] 의 점프 값은 1
제 3 조를 만족하지 않으면, 점프 값은 0
S2[x - 1] = S2[0] 이고 S2[x - 2] = S2[1] 이면, S2[x] 의 점프 값은 2
S2[x - 1] = S2[0] 이고 S2[x - 2] = S2[1] 이고 S2[x - 3] = S2[2] 이면, S2[x] 의 점프 값은 3
...

사람이 눈으로 위 방법에 따라 점프 값을 "육안 측정"하는 것이 가장 빠르지만, 같은 과정을 컴퓨터에 적용하는 것은那么容易하지 않습니다. 컴퓨터에는 컴퓨터가 좋아하는 방식이 있습니다.한 편의 간단한 블로그 글이 이 방식을 설명합니다

간단히 말하면——"점화식", 즉 알려진 첫 항이 -1, 두 번째 항이 0 임으로부터, 점화식으로 뒤의 모든 항을 얻습니다. 자세한 과정은 생략합니다. 위의 링크 블로그 글이 매우 명확하게 써 있습니다

아래에서 KMP 알고리즘의 구체적 과정을 얻을 수 있습니다:

패턴 문자열 S2 에 따라 점프 테이블 (next 테이블) 구축
S1 처음부터 비교 시작, next 테이블 조회하여 점프 값 얻고, S1 포인터를 오른쪽으로 이동하여 비교 계속, S1 끝까지

다시 말해 또 공간으로 시간을 교환하는 것입니다 (next 테이블이 점유하는 공간). 물론, 이 알고리즘에서 next 테이블은 패턴 문자열 S2 길이와 같은 선형 테이블일 뿐이며, 많은 공간이 필요하지 않습니다

삼.next 함수 구현

next 함수는 next 테이블 (점프 테이블) 을 구축하는 데 사용됩니다. next 테이블을 어떻게 구축하는가가 KMP 알고리즘의 핵심입니다 (KMP 의 증명 과정에关注하지 않는다면..). 링크 블로그 글의 방식에 따라 스스로 next 함수를 구현할 수 있습니다:

//参考例子：http://blog.sina.com.cn/s/blog_96ea9c6f01016l6r.html
#include<stdio.h>
void getNext(char a[], int n, int next[]){
int i, j;
next[0] = -1;//首元跳转值为 -1
next[1] = 0;//第二个元素跳转值为 0

for(i = 2; i &lt; n; i++){
	j = i - 1;
	
	//递推得到 next 表中剩余值
	while(j != -1){
		if(a[i - 1] == a[next[j]]){
			next[i] = next[j] + 1;
			break;
		}
		else{
			j = next[j];
		}
	}
}

}
main(){
char a[] = "abaabcac";//模式串 S2
int next[8] = {0};//跳转表，初始化为全 0
int i;
//构造 next 表
getNext(a, 8, next);
//输出 next 表
for(i = 0; i &lt; 8; i++){
	printf("%d ", next[i]);
}
printf("\n");

}

물론, 위의 getNext 함수는 아직 효율적이지 않은 것 같습니다 (이중 루프..). 하지만 장점은 이해하기 쉽다는 것입니다. 아래에서 책에 나온 next 함수를 봅시다:

#include<stdio.h>
void getNext(char a[], int n, int next[]){
int i, j;
i = 0;
next[0] = -1;//首元跳转值为 -1
j = -1;
//递推得到 next 表中剩余值
while(i &lt; n){
	if(j == -1 || a[i] == a[j]){
		++i;
		++j;
		next[i] = j;
	}
	else{
		j = next[j];
	}
}

}
main(){
char a[] = "abaabcac";//模式串 S2
int next[8] = {0};//跳转表，初始化为全 0
int i;
//构造 next 表
getNext(a, 8, next);
//输出 next 表
for(i = 0; i &lt; 8; i++){
	printf("%d ", next[i]);
}
printf("\n");

}

양자의 계산 결과는 같지만, 책에 나온 알고리즘은 이중 루프를 제거했습니다. 하지만 이렇게 한 결과는 코드를 더 복잡하게 만들었을 뿐이며, 실질적인 최적화는 아무것도 없습니다

뭐? 이중 루프를 제거했는데도 효율이 향상되지 않았다고? 말이 안 되죠? 카운터로 검증해 봅시다:

void getNext(char a[], int n, int next[]){
	int i, j;
	int counter = 0;///
next[0] = -1;//首元跳转值为 -1
next[1] = 0;//第二个元素跳转值为 0

for(i = 2; i &lt; n; i++){
	j = i - 1;
	
	//递推得到 next 表中剩余值
	while(j != -1){
		if(a[i - 1] == a[next[j]]){
			next[i] = next[j] + 1;
			counter++;///
			break;
		}
		else{
			j = next[j];
			counter++;///
		}
	}
}

printf("\n%d\n", counter);///

}
void getNext(char a[], int n, int next[]){
int i, j;
int counter = 0;///
i = 0;
next[0] = -1;//首元跳转值为 -1
j = -1;
//递推得到 next 表中剩余值
while(i &lt; n){
	if(j == -1 || a[i] == a[j]){
		++i;
		++j;
		next[i] = j;
		counter++;///
	}
	else{
		j = next[j];
		counter++;///
	}
}

printf("\n%d\n", counter);

}

P.S.구체적 조작 부분 (가장 내부의 if 블록과 else 블록) 에 counter++;를 삽입했습니다. 이렇게 얻은 결과만 비교 가능합니다 (알고리즘이 몇 회의 구체적 조작을 수행했는지)

실행 결과는 다음과 같습니다:

왼쪽 그림은 스스로 구현한 next 함수의 카운트 결과로, 이 4 단계가 적은 것은 바깥쪽 루프 횟수의 차이입니다 (책의 알고리즘은 n 회, 우리 알고리즘은 n-2 회). 우리 알고리즘의 바깥쪽 루프 횟수도 n 이라면, 14 회의 구체적 조작이 필요합니다 (우리는 단순히 간단한 최적화만 수행했을 뿐입니다)

두 개의 next 함수는 형식만 다를 뿐, 내부 조작 순서는 완전히 같습니다. next 함수를 이해하면, KMP 알고리즘에는 어려운 점이 없습니다 (S1 의 포인터가 백트래킹하지 않는 이유에关注하지 않는다면, 확실히 이것만이 유일한 어려운 점입니다..)

사.KMP 알고리즘 정확성의 증명

(본 글에서는 여기서 전개하지 않습니다. 나중에 이해하면 여기서 누락된 내용을 보충할지도 모릅니다. S1 의 포인터가 백트래킹하지 않는 이유, 왜 이전 부분이 다시 매칭될 수 없는지 자세히 설명합니다...)

하지만 순수하게 "구현"에关注한다면, next 함수만 이해하면 완전히 쉽게 KMP 알고리즘을 구현할 수 있습니다 (왜 이렇게 할 수 있는지, 왜 이렇게 하는 것이 맞는지의 증명.. 이는 수학자의 일입니다)

오.정리

KMP 알고리즘의 핵심은 next 테이블의 구축 과정이며, next 테이블을 구축하는 핵심 사상은 "점화식"입니다. 이를 이해하면, 완전히 몇 분 만에 KMP 알고리즘을 작성할 수 있습니다..

약간의 잡담:

KMP 알고리즘에도 변종이 있습니다. 본 글에서 논의하는 것은 가장 원시적인 KMP 알고리즘이며, 일반적인 변종에는:

next 테이블의 첫 번째 요소가 0(-1 이 아님). 최종적으로 얻는 결과는 우리 next 테이블의 각 요소에 +1 한 것으로, 단지 약속의 차이일 뿐입니다 (0 부터 시작하는가와 1 부터 시작하는가). 실질적인 차이는 없습니다
next 테이블 중에 여러 개의 -1 이 있음 (우리 결과에는 -1 이 하나만 있으며, 즉 next 테이블의 첫 번째 요소). 이는 실질적인 최적화로, 효율을 효과적으로 향상시킬 수 있습니다.実は next 테이블을 구축할 때 우리보다 한 단계 더 수행하며, 구축 과정이 조금 복잡해지지만, 매칭 알고리즘의 비교 횟수가 감소합니다