軟體設計師考試筆記--------資料結構基礎2：KMP算法
重點：必須學會部分比對表的計算方式以及最後考試例題的解法，幾乎必考！
1.1 KMP算法
*KMP算法是一種改進的字元串比對算法。
*KMP算法的關鍵是利用比對失敗後的資訊，盡量減少模式串與主串的比對次數以達到快速比對的目的。具體實作就是實作一個next()函數,函數本身包含了模式串的局部比對資訊。
*KMP算法的想法是，利用已經知道的前面六個字元“ABCDAB”，不要把“搜尋位置”移回已經比較過的位置，繼續把它向後移，這樣就提高了效率。
*學會計算《部分比對表》：
首先了解兩個概念：“字首”和“字尾”。
*”字首”指除了最後一個字元以外，一個字元串的全部頭 部組合；
*”字尾”指除了第一個字元以外，一個字元串的全部尾部組合。
*比對時移動的步數是用目前已比對字元串的長度減去已比對字元串中的最後一位在部分比對表中對應的值所得出的。
“部分比對值”就是“字首”和“字尾”的最長的共有元素的長度。以“ABCDABD”為例：
-“A”的字首和字尾都為空集，共有元素的長度為0；
-“AB”的字首為[A],字尾為[B]，共有元素的長度為0；
-“ABC”的字首為[A,AB],字尾為[BC,C]，共有元素的長度為0;
-“ABCD”的字首為[A,AB,ABC,]，字尾為[BCD,CD,D]，共有元素長度為0；
-“ABCDA”的字首為[A,AB,ABC,ABCD]，字尾為[BCDA,CDA,DA,A]，最長共有元素為”A”,長度為1；
-“ABCDAB”的字首為[A,AB,ABC,ABCD,ABCDA]，字尾為[BCDAB,CDAB,DAB,AB,B]，最長共有元素為“AB”,長度為2；
-“ABCDABD”的字首為[A,AB,ABC,ABCD,ABCDA,ABCDAB]，字尾為[BCDABD,CDABD,DABD,ABD,BD,D]，共有元素的長度為0。
得出：
考試例題：
在字元串的KMP模式比對算法中，需先求解模式串p的 next函數值，其定義如下。若模式串p為“abaabaca”，則其 next函數值為（B）
A．01111111 B．01122341 C．01234567 D．01122334
解： 給定的字元串叫做模式串T。j表示next函數的參數，其值是從 1到n，n是模式串T的長度。而k則表示一種情況下的next函數值。p表示其中的某 個字元，下标從1開始。看等式左右對應的字元是否相等。
式子思路：前面的式子計算時p1開頭，pk-1結尾，後面的式子同理。k以前所有符合條件的k，就是式子的長度，k值從符合條件的最大值開始依次遞減進行計算。
按照上述思路和公式具體計算如下：
1、j=1時，next[1]=0；
2、j=2時，k的取值為(1,j)的開區間，是以整數k是不存在的， 那就是第三種情況，next[2]=1；
3、j=3時，k的取值為（1，3）的開區間，k從最大的開始取值， 然後帶入含p的式子中驗證等式是否
成立，不成立k取第二大 的值。現在是k=2，将k導入p的式子中得，p1=p2，即 “a”=“b”，顯然不成立，舍去。k再取值就超出範圍了，是以 next[3]不屬于第二種情況，那就是第三種了，即next[3]=1；
4、j=4時，k的取值為（1，4）的開區間，先取k=3，将k導入p 的式子中得，p1p2=p2p3，不成立。 再取k=2，得p1=p3，成 立。是以next[4]=2；
5、j=5時，k的取值為（1，5）的開區間，先取k=4，将k導入p 的式子中得，p1p2p3=p2p3p4，不成立。 再取k=3，得 p1p2=p3p4，不成立。 再取k=2，得p1=p4，成立。是以 next[5]=2；
6、j=6時，k的取值為（1，6）的開區間，先取k=5，将k導入p 的式子中得，p1p2p3p4=p2p3p4p5，不成立。 取k=4，得 p1p2p3=p3p4p5，不成立。再取k=3，将k導入p的式子中得， p1p2=p4p5，成立。是以next[6]=3；
7、j=7時，k的取值為（1，7）的開區間，先取k=6，将k導入p 的式子中得，p1p2p3p4p5=p2p3p4p5p6，不成立。 再取k=5， 得 p1p2p3p4=p3p4p5p6 ，不成立。 再取k=4，得 p1p2p3=p4p5p6 ，成立。是以next[7]=4；
8、j=8時，k的取值為（1，8）的開區間， 先取k=7，将k導入 p的式子中得，p1p2p3p4p5p6=p2p3p4p5p6p7，不成立。 再 取k=6，得p1p2p3p4p5=p3p4p5p6p7，不成立。… 再取k=2， 得p1=p7，不成立。k再取值就超出範圍了，是以next[8]不屬 于第二種情況，那就是第三種了，即next[8]=1；結果如下：