一個效率非常高的字符串匹配算法
【基本思想】
利用部分匹配表比較字符串S是否包含字符串P
【步驟】
算出一張《部分匹配表》（Partial Match Table）--P
"部分匹配值"就是"前綴"和"后綴"的最長的共有元素的長度。
"前綴"指除了最后一個字符以外，一個字符串的全部頭部組合
"后綴"指除了第一個字符以外废离，一個字符串的全部尾部組合踪栋。
1. 部分匹配表
－ "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。
| A | AB | ABC | ABCD | ABCDA | ABCDAB | ABCDACD |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 2 | 0 |
2. next 數(shù)組
next 數(shù)組考慮的是除當前字符外的最長相同前綴后綴输吏。
計算某個字符對應(yīng)的 next 值权旷，就是看這個字符之前的字符串中有多大長度的相同前綴后綴，使其向右移動一位贯溅，然后初始值賦為 -1拄氯。
| A | B | C | D | A | B | D |
|---|---|---|---|---|---|---|
| A | B | C | D | A | B | D |
| -1 | 0 | 0 | 0 | 0 | 1 | 2 |
3. 遍歷比較
假設(shè)現(xiàn)在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置
- 如果 j = -1它浅，或者當前字符匹配成功（即 S[i] == P[j]）译柏，都令 i++，j++姐霍，繼續(xù)匹配下一個字符鄙麦；
- 如果 j != -1，且當前字符匹配失斈髡邸（即 S[i] != P[j]）胯府，則令 i 不變，j = next[j]恨胚。此舉意味著失配時骂因，模式串 P 相對于文本串 S 向右移動了 j - next [j] 位。
- 換言之与纽，當匹配失敗時侣签，模式串向右移動的位數(shù)為：失配字符所在位置 - 失配字符對應(yīng)的 next 值，即移動的實際位數(shù)為：j - next[j]急迂，且此值大于等于1影所。
【實例分析】
S[10] 跟 P[6] 匹配失敗。j = next[j]僚碎，即 j 從 6 變到 2（字符 D 對應(yīng)部分匹配表的值為0猴娩，對應(yīng)的 next 值為 2）
C 處再度失配
j = next[j] = 0
A 與空格失配，j = next[j] = -1。
i++,j++
【偽代碼】
假設(shè)現(xiàn)在文本串 S 匹配到 i 位置卷中，模式串 P 匹配到 j 位置
* 如果 j = -1矛双，或者當前字符匹配成功（即 S[i] == P[j]），都令 i++蟆豫，j++议忽，繼續(xù)匹配下一個字符；
* 如果 j != -1十减，且當前字符匹配失斦恍摇（即 S[i] != P[j]），則令 i 不變帮辟，j = next[j]速址。此舉意味著失配時，模式串 P 相對于文本串 S 向右移動了 j - next [j] 位由驹。
【代碼實現(xiàn)】
int KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen)
{
//①如果j = -1芍锚，或者當前字符匹配成功（即S[i] == P[j]），都令i++蔓榄，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1并炮，且當前字符匹配失敗（即S[i] != P[j]）润樱，則令 i 不變渣触，j = next[j]
//next[j]即為j所對應(yīng)的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
【性能分析】
O(n+m)
