KMP算法，C語言實作

研究了兩天，終于把KMP算法整明白了，貼個代碼

參考連結：https://www.bilibili.com/video/BV1iJ411a7Kb?p=1&vd_source=b5fa7d9756fa49e4552b8f222264fc66

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 建構 d 數組*/
static void get_next(int* d,const char* p) {
	int i = 1;
	int j = 0;
	
	d[0] = 0;					// 第一個字元不參與比對過程

	int len_p = strlen(p);
	while (i < len_p) {	
		if (p[i] == p[j]) {		
			d[i++] = ++j;		// 字元比對成功,此時的d[i]就是比對成功的前字尾長度（j+1）
		} else {
			if (j > 0) {
				// 字元比對失敗,但此時并不能直接将d[i]置0,因為在p[0] ~ p[j-1]之間可能還存在公共前字尾,是以還要繼續比對
				j = d[j - 1];	
			} else {
				i++;
			}
		}
	}
}

/* kmp模式比對 */
static int kmp(const char* t, const char* p) {
	int* d;						// d數組（表示p[0] ~ p[i] 範圍之間的最大公共前字尾） 需要初始化為 0
	int i = 0;					// 主串下标索引
	int j = 0;					// 模式串下标索引

	int len_t = strlen(t);		// 主串長度
	int len_p = strlen(p);		// 模式串長度

	/*********************  列印區 友善測試  *************************/
	for ( i = 0; i < len_t; i++) {
		printf("%2d ", i);
	}
	printf("\n");
	for (i = 0; i < len_t; i++) {
		printf("%2c ", t[i]);
	}
	printf("\n");
	for (i = 0; i < len_p; i++) {
		printf("%2c ", p[i]);
	}
	printf("\n");
	/*********************  列印區 *************************/

	d = (int*)malloc(sizeof(int) * len_p);
	if (!d) {
		printf("配置設定失敗！");
		exit(0);
	}
	memset(d, 0, len_p * sizeof(int));		

	get_next(d, p);

	i = 0;
	while (i < len_t) {
		if (t[i] == p[j]) {			// 字元比對
			i++;
			j++;
			if (j == len_p) {		// 找到了
				//return i - j;
				return i - len_p;
			}
		} else {					// 失配
			if (j > 0) {
				j = d[j - 1];		// 保持i不變,将 j 指向 d[j - 1] (p[0] ~ p[j-1] 範圍之間的最大公共前字尾的長度）
			} else {
				i++;				// j == 0,說明沒有公共前字尾,将i往後面移動一位
			}
		}
	}

	free(d);
	return -1;						// 沒找到，傳回-1
}

int main() {
	printf("%d\n**************\n", kmp("ABABABABC", "ABABC"));
	printf("%d\n**************\n", kmp("ABABABABC", "ABAB"));
	printf("%d\n**************\n", kmp("ABABCABAB", "ABAB"));
	printf("%d\n**************\n", kmp("AAAAAAA", "AAA"));
	printf("%d\n**************\n", kmp("ABABABC", "ABABC"));
	printf("%d\n**************\n", kmp("XYXZdeOXZZKWXYZ", "WXYZ"));
	printf("%d\n**************\n", kmp("GCAATGCCTATGTGACCTATGTG", "TATGTG"));
	printf("%d\n**************\n", kmp("AGATACGATATATAC", "ATATA"));
	printf("%d\n**************\n", kmp("CATCGCGGAGAGTATAGCAGAGAG", "GCAGAGAG"));
	return 0;
}
           

---------------------------------------------------------------------------

測試結果：