字元串比對——KMP算法

關于KMP算法的分析，我覺得這兩篇部落格寫的不錯：

http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html

http://blog.csdn.net/v_JULY_v/article/details/6545192

下面的筆記也是參考了這兩篇部落格的。

KMP算法是最有名的字元串比對算法了。它是

BF算法

的改進版，至于是如何改進的，先引用上述第二篇部落格裡的一段話：

        “在繼續分析之前，咱們來思考這樣一個問題：為什麼快排或者堆排序比直接的選擇排序快？直接的選擇排序，每次都是重複地比較數值的大小，每掃描一次，隻得出一個最大（小值），再沒有其它的成果。而快排，每掃一次，将資料分成了兩部分，右邊的資料都大于左邊的資料，是以在下一次比較的時候，這兩部分元素之間就不用比較了。再看堆排序，建堆的過程也是O(n)的比較，但比較的結果得到了最大（小）堆這種三角關系，之後的比較就不用再每一個都需要比較了。

        由上述思考，咱們總結出了一點優化的歸律：采用一種簡單的資料結構或者方式，将每次重複性的工作得到的資訊記錄得盡量多，友善下一次做同樣的工作，這樣将帶來一定的優化。”

總結上面這段話的核心思想，就是把循環中要重複做的工作提取到循環外完成，進而提高效率。

下面用一個例子示範KMP比對的過程。其中涉及的三個資料如下：

        source：源串，即要比對的母船

        pattern：模式串，即子串

        next數組：其每個元素對應pattern的每個字元，表示當該字元pattern[j]不比對source[i]時，應該從pattern的哪個下标開始重新比對目前的source[i]，具體求法後面介紹

本例中source為ABCABCABDE，pattern為ABCABD，第一次比對，前5個字元均比對成功，比對第6個字元時如下：

此時發現source[5]和pattern[5]不比對，BF算法的做法是從source[1]開始從新比對pattern，即像下面這樣：

而KMP算法則不會再去重新比較source[1...4]了，它會利用next的資訊調整pattern。因為next[5]=2，是以下一次比對将目前的source[5]和pattern[2]比較，即像下面這樣：

這時發現source[5]和pattern[2]比對，繼續往下比較，直至pattern中是以元素都比較完了，如下：

此時已經在母串中找到了子串，i=9，m=6，是以傳回的下标為i-m=3。

這樣整個比對過程就完了，感覺不過瘾嗎，前面兩篇推薦的部落格裡有更長的比對串分析。

把上面的過程翻譯成代碼，也就是KMP算法的實作，如下：

int KMP(char *source, char *pattern)
{
	int i, j, m, n;
	int *next;

	i = 0;
	j = 0;
	m = strlen(pattern);
	n = strlen(source);
	next = (int *)malloc(m * sizeof(int));

	Next(pattern, next);<span style="white-space:pre">	</span>// 這是求next數組的函數，後面解釋

	while (i < n && j < m)
	{
		if (j == -1 || source[i] == pattern[j])
		{
			++i;
			++j;
		}
		else
		{
			j = next[j];
		}
	}

	free(next);

	if (j == m)
	{
		return i - m;
	}
	else
	{
		return -1;
	}
}      

下面來看next數組是如何求得的。

如前所述，next數組裡儲存的就是pattern[j]與母串中的字元不比對時，該用哪個下标繼續和這個字元比對。若next[j]=k，則有：pattern[0...k-1] = pattern[j-k...j-1],而且這個k是最大的，即不會有pattern[0...k] =pattern[j-k-1...j-1]。

反過來想，如果已經知道了pattern[0...k-1] = pattern[j-k...j-1]，next[j]是多少呢？要分兩種情況考慮：

        1. pattern[k] != pattern[j]，則next[j] = k

        2. pattern[k] = pattern[j]，則next[j] = next[k]

第二種情況是因為，若pattern[k] = pattern[j]時，也使next[j]=k；則在pattern[j]于母串不比對的情況下，再拿pattern[next[j]]即pattern[k]去比較的話，肯定也是不比對的。這是隐藏的重複工作。使next[j] = next[k]就能避免這種重複工作。

那麼怎麼又能保證pattern[j]不會等于pattern[next[k]]呢？不急，一步一步想：最開始有next[0]=-1，如果pattern[1]=pattern[0]，那麼由規則2，next[1]=next[0]=-1；再如果pattern[2]=pattern[1]，那麼next[2]=next[1]=-1。看到了嗎，三個一樣的字元，如果是next依次為前一個元素的情況，最終都會是最前面那個next值，這就保證了最大的減少重複工作。

好吧，上面的解釋很挫，意會吧。其實就跟離散樹一樣，同一個集合的元素都有相同的根。

有了上面的規則後，求next數組就比較友善了。用動态規劃的政策很好實作：

void Next(char *pattern, int *next)
{
	int i, j, n;

	i = 0;
	j = -1;
	next[0] = -1;
	n = strlen(pattern);

	while (i < n - 1)
	{
		if (j == -1 || pattern[i] == pattern[j])
		{
			++i;
			++j;

			if (pattern[i] != pattern[j])
			{
				next[i] = j;
			}
			else
			{
				next[i] = next[j];
			}
		}
		else
		{
			j = next[j];
		}
	}
}      

是不是感覺和KMP的架構很像，其實就是一回事，都是子串比對，都利用了next數組。

不同之處在于：KMP是source比對pattern，Next是一直從pattern的頭部開始比對後面所有的序列；在Next裡面，next數組還沒有完全生成，是利用前面生成的next加上比對結果生成下一個next，這就是動規的政策。