問題
目錄
- KMP是什么，做什么用的
- KMP算法的高效體現(xiàn)在哪
- 如何KMP算法的next數(shù)組
- KMP的代碼
- KMP的時(shí)間復(fù)雜度是多少
有句話很有趣：Stay hungry, stay foolish. 個(gè)人根據(jù)對(duì)這句話的理解 以一個(gè)有強(qiáng)烈求知欲的小白的角度譬重，用提問解答的方式組織全文拱礁，以此發(fā)現(xiàn)自己知識(shí)圖譜的不足并積極學(xué)習(xí)新的知識(shí)熟妓。
看法
KMP是什么，做什么用的
KMP全稱為Knuth Morris Pratt算法，三個(gè)單詞分別是三個(gè)作者的名字。KMP是一種高效的字符串匹配算法卑硫，用來在主字符串中查找模式字符串的位置(比如在"hello,world"主串中查找"world"模式串的位置)。
KMP算法的高效體現(xiàn)在哪
高效性是通過和其他字符串搜索算法對(duì)比得到的庞钢，在這里拿BF(Brute Force)算法做一下對(duì)比拔恰。BF算法是一種最樸素的暴力搜索算法。它的思想是在主串的[0, n-m]區(qū)間內(nèi)依次截取長度為m的子串基括，看子串是否和模式串一樣(n是主串的長度颜懊，m是子串的長度)。代碼是這樣:
func bf(main, pattern string) int {
if len(main) == 0 || len(pattern) == 0 || len(main) < len(pattern) {
return -1 // 異常判斷风皿，若不存在返回-1
}
n, m := len(main), len(pattern)
for i := 0; i <= n-m; i++ { // 結(jié)束條件是n-m,不需要到n
sub := main[i : i+m] //截出主串中的對(duì)比串
if sub == pattern {
return i //返回索引值
}
}
return -1 // 主串中不存在模式串
}
BF的時(shí)間復(fù)雜度是O(NN)河爹，存在很大優(yōu)化空間。當(dāng)模式串和主串匹配時(shí)桐款，遇到模式串中某個(gè)字符不能匹配的情況咸这，對(duì)于模式串中已經(jīng)匹配過的那些字符，如果我們能找到一些規(guī)律魔眨，將模式串多往后移動(dòng)幾位媳维，而不是像BF算法一樣酿雪，每次把模式串移動(dòng)一位，就可以提高算法的效率侄刽。比如說在"ababaababacd"中查找"ababac"*指黎，可以避免一些字符之間的比較。
下面通過一個(gè)具體的例子來看看可以跳過的情況州丹。比如主模式串是"ababaeaba",模式串是"ababacd",在BF算法中醋安，遇到不匹配的情況是這樣處理的:
main: "ababaeaba" // 例如這兩個(gè)串，當(dāng)sub為"ababaea"時(shí)和"ababacd"進(jìn)行對(duì)
pattern: "ababacd" // 比墓毒，當(dāng)main[i]為e時(shí)吓揪，發(fā)現(xiàn)和pattern[j]的值e不一致，BF
// 的做法是去下一個(gè)sub,即用"babaeab"和pattern進(jìn)行比較所计。
我們希望找到一些規(guī)律柠辞，遇到兩個(gè)字符不匹配的情況時(shí)，希望可以多跳幾個(gè)字符醉箕，減少比較次數(shù)钾腺。KMP算法的思想是：在模式串和主串匹配過程中，當(dāng)遇到不匹配的字符時(shí)讥裤，對(duì)于主串和模式串中已對(duì)比過相同的前綴字符串放棒，找到長度最長的相等前綴串，從而將模式串一次性滑動(dòng)多位己英，并省略一些比較過程间螟。在上個(gè)例子，KMP算法中损肛，是這樣處理的：
main: "ababaeaba" // 比如main中的"ababa"子串厢破，對(duì)標(biāo)為[2~4]的"aba"和pattern中下
pattern: "ababacd" // 標(biāo)為[0~2]的"aba"相同,此時(shí)可以滑動(dòng)j-k位,即j=j-k。(其中j是
// pattern中"c"的下標(biāo),k是"abc"的長度)治拿。
"ababaeaba" // 比較過程中摩泪，main[5]為"e"和pattern[5]為"c"不匹配，但是兩個(gè)
"ababacd" // 串中都有相同的"aba"前綴,所以可以滑動(dòng)j-k位
|
∨
"ababaeaba"
"ababacd"
| // 滑動(dòng)j-k位后發(fā)現(xiàn)main[5]和patterb[3]不相同劫谅，需要再次滑動(dòng)
∨
"ababaeaba"
"ababacd" // 滑動(dòng)過程和上次類似见坑。
通過這個(gè)例子可以看出，每次滑動(dòng)的位數(shù)是j-k捏检，滑動(dòng)位數(shù)和主串無關(guān)荞驴，僅通過模式串就可以求出。在KMP算法中通過next數(shù)組來存儲(chǔ)當(dāng)兩個(gè)字符不相等時(shí)模式串應(yīng)該移動(dòng)的位數(shù)贯城。
如何KMP算法的next數(shù)組
再次明確next數(shù)組的含義 : next數(shù)組用來存模式串中每個(gè)前綴最長的能匹配前綴子串的結(jié)尾字符的下標(biāo)熊楼。 next[i] = j 表示下標(biāo)以i-j為起點(diǎn)，i為終點(diǎn)的后綴和下標(biāo)以0為起點(diǎn)能犯，j為終點(diǎn)的前綴相等鲫骗，且此字符串的長度最長犬耻。用符號(hào)表示為p[0~j] == p[i-j~i]。下面以"ababacd"模式串為例挎峦，給出這個(gè)串的next數(shù)組香追。
| 模式前綴 | 前綴結(jié)尾下標(biāo) | 最長能匹配前綴子串結(jié)尾字符的下標(biāo) | next數(shù)組的取值 | 匹配情況 |
|---|---|---|---|---|
| a | 0 | -1 | next[0] = -1 | 無 |
| ab | 1 | -1 | next[1] = -1 | 無 |
| aba | 2 | 0 | next[2]=0 | pattern[2]==pattern[0] |
| abab | 3 | 1 | next[3]=1 | pattern[2:4]==pattern[0:2] |
| ababa | 4 | 2 | next[4]=2 | pattern[2:5]==pattern[0:3] |
| ababac | 5 | -1 | next[5]=-1 | 無 |
KMP的代碼
下面給出KMP算法的完整代碼合瓢，里面有詳細(xì)的注釋坦胶。注意Go語言版本的代碼模式串和主串的下標(biāo)都是從0開始的，C++版本的代碼從1開始晴楔，你可以比較一下兩種下標(biāo)代碼的區(qū)別顿苇。
Go
func kmp(s string, pattern string) int {
n, m := len(s), len(pattern)
if n < m {
return -1
}
next := make([]int, m)
// 把next數(shù)組中全部初始化為-1
for index := range next {
next[index] = -1
}
//求next數(shù)組中的值
for i := 1; i < m-1; i++ { // i從1開始,因?yàn)榈谝粋€(gè)字符如果比較失敗了,需重新開始匹配 // i取不到m-1的值, 因?yàn)槿〉絤-1意味著整個(gè)字符串都相等
j := next[i-1] // 前i-1的值是之前循環(huán)中比較過的,這里j初始化為next[i-1]
for pattern[j+1] != pattern[i] && j != -1 { // 因?yàn)檫@里是pattern[i]和pattern[j+1]進(jìn)行比較
j = next[j] // 所以這里j是退回到next[j]的位置再進(jìn)行循環(huán)比較
}
if pattern[j+1] == pattern[i] { //因?yàn)槊看窝h(huán)只會(huì)新增一個(gè)字符,所以這里用if判斷一個(gè)新字母即可.
j++ // 如果相等則j++
}
next[i] = j // 當(dāng)前的取值
}
// 匹配的過程
j := 0 //模式串從0下標(biāo)開始匹配
for i := 0; i < n; i++ {
for j > 0 && s[i] != pattern[j] { // j>0意為j沒有退回起點(diǎn) //s[i] != pattern[j]意為兩個(gè)字符出現(xiàn)不匹配的情況
j = next[j-1] + 1 // pattern[j]和s[i]不一致,說明前next[j-1]是匹配的,所以移動(dòng)next[j-1]位;因?yàn)閟[i]要繼續(xù)和pattern[j]進(jìn)行比較,所以j還需加1
}
if s[i] == pattern[j] {
if j == m-1 { //因?yàn)閖從下標(biāo)0開始,所以m需減1,兩者相等說明循環(huán)了len(m)次
return i - m + 1
}
j++ //否則繼續(xù)判斷下一個(gè)字符
}
}
return -1
}
C++
#include <iostream>
using namespace std;
const int N = 10010, M = 100010;
int n, m;
int ne[N];
char s[M], p[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1;
for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
for (int i = 1, j = 0; i <= m; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == n)
{
printf("%d ", i - n);
j = ne[j];
}
}
return 0;
}
如果看了注釋之后還是對(duì)代碼有疑問，可以通過下面的測(cè)試用例打斷點(diǎn)觀察代碼的運(yùn)行過程税弃。
func main() {
a := "ababaababacd"
b := "ababac"
fmt.Print(kmp(a, b))
}
KMP的時(shí)間復(fù)雜度是多少
KMP的時(shí)間復(fù)雜度是O(n), 證明方法如下纪岁。
//1.kmp兩個(gè)循環(huán)類似,分析一個(gè)即可
for i := 0; i < n; i++ { //4. 兩個(gè)循環(huán)的時(shí)間復(fù)雜度是O(2n),所以KMP的時(shí)間復(fù)雜度是O(n)
for j > 0 && s[i] != pattern[j] {
j = next[j-1] + 1 //3. 這里j會(huì)減值,由于next[j-1]肯定小于j,所以j最多減n次
}
if s[i] == pattern[j] {
if j == m-1 {
return i - m + 1
}
j++ //2. 在循環(huán)中,每次循環(huán)j最多+1,所以j最多加n次
}
}
本文涉及到的算法代碼已上傳至常見筆試算法-Go語言版本，歡迎讀者去點(diǎn)star~
歡迎關(guān)注我的公眾號(hào): 薯?xiàng)l的自我修養(yǎng)
本公眾號(hào)有對(duì)應(yīng)讀者群则果，贊賞后可加入幔翰。可私信我微信709834997西壮，備注：申請(qǐng)加入薯?xiàng)l公號(hào)讀者群遗增。
