背景

字符串模式匹配，普通模式非常好理解，拿著模式串依次與主串做比較，知道完全匹配，但是這種算法，主串得不斷地回溯，時(shí)間復(fù)雜度O(n*m)。

唐納德·克努特

有沒(méi)有降低時(shí)間復(fù)雜度的可能，唐納德·克努特等人想到了一種辦法不用使主串不停地回溯，而每次使模式串的某個(gè)字符與主串的待比較字符對(duì)齊，這個(gè)算法簡(jiǎn)稱KMP。求解模式串的哪個(gè)字符該與這次比較的主串字符對(duì)齊，是KMP算法的核心，簡(jiǎn)稱next函數(shù)或失配函數(shù)。這種算法求解復(fù)雜度降低到O（n+m）。

next函數(shù)語(yǔ)義

next[j]=k表達(dá)的意思是從模式串的 1~j-1 組成的子模式串，最長(zhǎng)相同的前、后綴的長(zhǎng)度為 k-1。舉例說(shuō)明，如下的字符串，next[6]=3，因?yàn)榫幪?hào)為6的字符c的最長(zhǎng)前綴為編號(hào)為1的a ，編號(hào)為2的b 字符，最長(zhǎng)后綴為編號(hào)為4的字符，編號(hào)為5的字符b，所以 k=3。

12345678

a	b	a	a	b	c	a	c

再看一下失配函數(shù)next[j]的嚴(yán)格定義，模式串字符的編碼從1開(kāi)始。

next函數(shù)分析

next 函數(shù)值僅取決于模式串本身而與相匹配的主串無(wú)關(guān)。從next函數(shù)的定義出發(fā)用遞推的方法求next函數(shù)值。

由定義得知 next[1]=0，設(shè)next[j]=k，這表明在模式串中存在下列關(guān)系

"P1...Pk-1" = "Pj-k+1...Pj-1"

圖形化顯示（一條豎線表示一個(gè)字符）：

其中k為滿足1 < k < j的某個(gè)值，并且不能存在k’ > k滿足上個(gè)等式。此時(shí) next[j+1]=? 分兩種情況討論，

1）若 Pk = Pj ，則 next[j+1] = next[j] + 1 ，即 k + 1 ，如下圖顯示：

2）若Pk不等于Pj，如下圖所示，我們把如下字符，看成一個(gè)字符串，尋找它的最長(zhǎng)相同的前、后綴：

"P1...Pj+1"

此時(shí)我們已知一個(gè)條件：

"P1...Pk-1" = "Pj-k+1...Pj-1"

也就是在上圖中2個(gè)黃色區(qū)域表示的前、后綴字符串相等，這樣我們依然在上圖中的左側(cè)黃色部分中尋找。最終找到了2塊咖啡色區(qū)域 1~k’-1， k-k’+1~k-1 相等，根據(jù)next函數(shù)的定義，便是：

next[k]=k'

并且我們根據(jù)已知條件 ‘P1…Pk-1’ = ‘Pj-k+1…Pj-1’，可以推導(dǎo)出在右側(cè)黃色區(qū)域也存在這樣的咖啡色區(qū)域，根據(jù)等式傳遞，我們可以得出：

"P1...Pk'-1" = "Pj-k'+1...Pj-1"

因?yàn)镻j不等于Pk，所以我們新找出了一個(gè)k’（很顯然1 < k’ < k），如果它真的滿足了 Pj=Pk’，則 next[j+1] = k’ + 1 ，即 :

next[j+1] = next[k] + 1

如果它很遺憾地又不等于Pj，也沒(méi)關(guān)系，我們繼續(xù)在[1,k’]這個(gè)區(qū)間內(nèi)找這樣的K點(diǎn)，如果真的不存在這樣的k’，那么 根據(jù)定義可以得出：

next[j+1]=1

失配函數(shù)代碼實(shí)現(xiàn)

/// <summary>/// 失配函數(shù)/// </summary>/// <param name="p">模式字符串（編碼從索引位置1開(kāi)始）</param>/// <returns>模式字符串中每個(gè)字符的失配值數(shù)組</returns>private static int[] getNext(char[] p){int[] next = new int[p.Length];next[1] = 0;int j = 1;int k = 0;while (j < p.Length - 1){if (k == 0 || p[j] == p[k]){next[++j] = ++k; //上述分析中的k'+1賦值給next[j+1]}else{k = next[k]; //next[k]賦值給k，相當(dāng)于上述分析中的k'}}return next;}

模擬分析

模擬失配函數(shù)求解的整個(gè)過(guò)程代碼。

static void Main(string[] args){string pattern = "abaabcac";char[] pcharsfrom1 = preOperate(pattern);Console.WriteLine();int[] next = getNextWithTest(pcharsfrom1);printf(next);Console.ReadLine();}

預(yù)處理字符串，將字符串整體后移1位

/// <summary>/// 預(yù)處理字符串，將字符串整體后移1位/// </summary>/// <returns></returns>private static char[] preOperate(string pattern){char[] pchars = pattern.ToCharArray(0, pattern.Length);char[] pcharsfrom1 = new char[pchars.Length + 1];for (int i = pchars.Length; i > 0; i--)pcharsfrom1[i] = pchars[i - 1];return pcharsfrom1;} private static int[] getNextWithTest(char[] p){int[] next = new int[p.Length];next[1] = 0;int j = 1;int k = 0;printf(p);while (j < p.Length - 1){if (k != 0)Console.WriteLine("p[{0}]（{1}） == p[{2}]（{3}）??", j, p[j], k, p[k]);if (k == 0 || p[j] == p[k]){if (k == 0){++j;++k;next[j] = k;Console.WriteLine("根據(jù)k=0得出：p[{0}]={1}", j, k);Console.ForegroundColor = ConsoleColor.DarkGreen;Console.WriteLine("--------------------------------");Console.ForegroundColor = ConsoleColor.White;}else{++j;++k;next[j] = k;Console.WriteLine("根據(jù)p[j] == p[k]得出：p[{0}]={1}", j, k);Console.ForegroundColor = ConsoleColor.DarkGreen;Console.WriteLine("--------------------------------");Console.ForegroundColor = ConsoleColor.White;}}else{k = next[k];}}return next;}private static void printf<T>(T[] p){int eachlineCount = 10;for (int line = 0; line < p.Length / eachlineCount + 1; line++){for (int i = 0; i < eachlineCount && line * eachlineCount + i < p.Length; i++){Console.Write(" {0} ", line * eachlineCount + i);}Console.Write("\n");for (int i = 0; i < eachlineCount && line * eachlineCount + i < p.Length; i++){if (line == 0)Console.Write(" {0} ", p[line * eachlineCount + i]);else{Console.Write(" {0} ", p[line * eachlineCount + i]);}}Console.Write("\n\n");}}

模擬結(jié)果展示：

源碼下載：

http://download.csdn.net/detail/daigualu/9791023

總結(jié)

以上是生活随笔為你收集整理的算法-发明KMP算法的唐纳德·克努特是怎么想到失配函数next[j]的？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。