KMP—C語言實作

這是我的第一篇部落格，希望以後可以堅持下去！

KMP原理：

     KMP是在字元串中尋找特定子串的算法。假設：給定字元串：S = "abcdefabcdex" ，下标用i表示；子串：T = "abcdex"，下标用j表示；

     我們希望在S中找到字串T，正常的方法是從S的第一個字元'a'與T的第一個字元'a'進行比較，然後依次比下去...當S找到"abcde"時，T也找到"abcde"，哈哈還有一 個就成功了，但是我們的運氣不太好，S的下一個字元是'f'而T的下一個字元是'x'，這個時候按照一般的算法會回溯S的下标i到字元‘b'，然後重複上面的步驟，這裡就有一個問題，當我們比較S的"abcde"和T的"abcde"的時候可以得到一個資訊，那就是S的第一個字元’a' 後面的四個字元（即'b''c''d''e'）并沒有與T的一個字元相同的字元,一般的算法并沒有用到這個資訊，而KMP就利用這個資訊進而不必回溯S的下标i，隻要回溯T的下标j（

這裡注意因為字串T中也會有重複的字元，是以j并不需要每次都回溯到第一個字元

），KMP實作的關鍵就是j的回溯規則。通過分析j的回溯隻跟字元串T有關，通過T建立j的回溯規則數組next,next[j]的值就是位置j要回溯的位置。

C語言實作代碼：

// 建立next數組
int mknext(char const*T, int *next) {
	int len = strlen(T);
	int i = 0;
	int j = -1;
	next[0] = -1;
	while (i < len) {
		if (j == -1 || T[i] == T[j]) {
			i++;
			j++;
			next[i] = j;
		}
		else
			j = next[j];
	}
	return 0;
}
           

//KMP實作
int index_KMP(char const*S, char const*T, int pos) {
	int i = pos-1;
	int j = -1;
	int next[LIM];
	mknext(T, next);
	int S_len, T_len;
	S_len = strlen(S);
	T_len = strlen(T);
	while (i < S_len && j < T_len) {
		if (S[i] == T[j] || j == -1) {
			i++;
			j++;
		}
		else
			j = next[j];
	}
	if (j >= T_len)
		return i - T_len;
	else
		return -1;
}           

這裡有一個小問題：字元串數組作為函數形參聲明的時候要用char const*,不能是const char*。