文章目錄
- KMP算法
- 前言
- 1.KMP算法概述
- 2.next數組
- 3.KMP實作
-
- KMP的簡單應用：
-
- [J - 剪花布條](https://vjudge.net/problem/HDU-2087)
-
- 題意：
- 思路：
- 來自作者最真誠的吐槽
KMP算法
字元串比對算法，是在實際工程中經常遇到的問題，也是各大公司筆試面試的常考題目。此算法通常輸入為原字元串（string）和子串（pattern），要求傳回子串在原字元串中首次出現的位置(做題的時候變化挺多的，基本上沒有隻傳回首次出現的位置，一般都是傳回所有的位置，或者出現的次數，還有讓你列印出next數組)。比如原字元串為“ABCDEFG”，子串為“DEF”，則算法傳回3。常見的算法包括：BF（Brute Force，暴力檢索）、RK（Robin-Karp，哈希檢索）、KMP（教科書上最常見算法）、BM（Boyer Moore）、Sunday等。今天我來介紹一下KMP算法，以及基本的代碼實作和每一步的原理分析……
前言
我覺得KMP算法比較容易了解，你要是認真看了阮大神的KMP文章，基本上就明白他的原理了(懂是懂，但是看不懂算法？！ ……)其實就有兩部分比較重要，第一個是next數組的建構，另一個就是如何實作他的字元比對。(我手推了一下下，發現十行代碼之間，KMP灰飛煙滅，屬實有點神奇!!!)
1.KMP算法概述
首先還是簡單介紹一下KMP與傳統的暴力比對算法的不同點在哪裡，難點在哪裡。
我們先來看一下暴力的字元串比對算法
// 暴力比對（僞碼）
int search(String pat, String txt) {
int M = pat.length;
int N = txt.length;
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++) {
if (pat[j] != txt[i+j])
break;
}
// pat 全都比對了
if (j == M) return i;
}
// txt 中不存在 pat 子串
return -1;
}
對于暴力算法，如果出現不比對字元，會同時回退
txt
和
pat
指針，時間複雜度為
O(MN)
,空間複雜度為
O(1)
,最主要的問題是，如果字元串中重複的字元較多，該算法就很蠢。
比如
tex
= ‘’ aaacaaab’’，
pat
= ‘‘aaab’’:
很顯然
pat
中跟本沒有c，導緻在c這裡比較了4次，根本沒有必要退回指針
i
，暴力算法很明顯做了不必要的操作。
KMP優秀就優秀在他花費了一些空間來記錄一些資訊，來解決上述的情況
比如
txt
= “aaaaaaab”,
pat
= “aaab”,暴力算法會和上面那個例子一樣蠢蠢的傳回指針i，而kmp算法就會耍小聰明
因為KMP算法知道b字元之前的a都是比對的，是以每次隻需比較b是否被比對即可
KMP永遠不會回退
txt
的指針，就像 我高中曉明老師說的好：不走回頭路。（就是不會重複掃描
txt
），而是借助next數組的資訊把
pat
移動到正确的位置繼續比對.
這個算法的難點在于如果計算next函數的資訊？如何根據這些資訊正确的移動
pat
的指針？
是以我們接下來來解決一下next數組
2.next數組
咱們再舉個栗子
txt
= “BBC ABCDAB ABCDABCDABDE”
pat
= “ABCDABD”
我們要求的是
pat
的next數組
首先next數組其實是字元串的部分比對表，由部分搜尋詞和部分比對值組成
搜尋詞就是
pat
的每一個元素
部分比對值就是字首和字尾的最長共有元素長度
在這之前，我們要先知道什麼是字首和字尾。
字首是指除了最後一個字元以外的，一個字元串的全部頭部組合；
字尾是指除了第一個字元以外的，一個字元串的全部尾部組合
比如字元串“bread”
字首：b, br, bre, brea
字尾：read， ead， ad，d
對于
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。
看到這裡你應該明白什麼是next數組了，但是你心中一定有個疑惑，我怎麼用代碼實作呢？？？
别急，聽我慢慢道來
你先觀察一下上面那個ABCDABD，你會發現第二個A出現的時候，其比對值就是1，而他後面的B如果和第一個A後面的字元相等，那他的比對值就是2，一看，确實是一樣的B，是以就變成了2。
其實是這麼一個過程：你是從第一個開始求，但是第一個字元隻有一個元素，故沒有字首和字尾，就是0，然後你就開始比較第二個，一看，A != B,是以也是0，再看三四，都是0，直到你看到了第五個，第五個的A == 第一個的A ，一看比對成功，我們就記錄第五個數的比對值是1。再就比較下一個字元，也就是第六個。這個時候細心的同學就會問：哎呀，你怎麼就判斷了這一個元素就判定他是1，而不去周遊看看他的所有字首字尾有沒有其他的一樣的，而且長度還超過1的？其實第i個是在第i- 1 的基礎上進行的，如果第i個與前面那個比對了，就在第i- 1的基礎上加1.等你看第6和7個字元就明白了，因為第五個字元與第一個字元比對了，我們就把第六個字元與第二個字元比較一下，實作了“移動”。這個時候發現第六個和第二個字元是相等的，是以第6個的部分比對值就在第五個的基礎上加1，1 + 1 = 2，就是2.。你寫一下想一想，就能明白是什麼意思。然後我們在看第七個與第三個比較，一看C != D，比對失敗，就為0.這個時候如果還有第八個元素，那第八是要和第一個重新比較的，因為第七個已經比對失敗，是以他的字首字尾共有元素最多就是1（當且僅當第八個和第一個比對成功）。
next構造的代碼奉上
int next1[1000005];
void getnext()//打表，構造出next數組(這也太神奇了吧這個法)
{
int j, k;
j = 0;
k = -1;
next1[0] = -1;//當字元串隻有一個元素的時候，就沒有字首和字尾，是以直接指派為0；
while(j < m)//表面上看其實可以換成從j從1到m的for循環的,但實際上你要是手推一波你就會發現這個循環不止進行了m-1次，這就是神奇所在
{
if(k == -1 || ss[j] == ss[k])//這個ss[j] 其實就是到最後一個元素，而ss[k] 其實就是第k個元素，看看這兩個想不想等
next1[++j] = ++k;
else
k = next1[k];
/*這個就是用來清值的，因為每次求第j個的時候，如果不比對，就得清值，有可能求一個next1的值時不止用了一次這個玩意，很神奇*/
}
}
這個是我手推的一遍循環過程（不推不知道，一推才知道其中的奧秘）
3.KMP實作
這個地方就要看如何靈活運用next數組的資料進行跳躍了……
（你可以當做闆子背下來）
void kmp()
{
int ans = 0;//用來記錄出現幾次
int i = 0;//i是用來記錄被搜字元串的位置
int j = 0;//j是用來記錄要搜的字元串的位置
getnext();
for(int i = 0; i < n; i++)
{
while(j > 0 && s[i] != ss[j])//就在這一步，實作了跳躍!,因為j = next[j],進而在i的地方進行s[i]與ss[j]的新的比較
j = next1[j];
if(s[i] == ss[j])//主要是用來找第一次比對的位置
j++;
if(j == m)//當找到一次以後就輸出這個位置
{
ans ++；//找到一次就直接++，計算次數用
cout<<i - m + 2 <<'\n';//這個地方是輸出位置的，不知道的話就直接背過就完事了了，咱也不知道為什麼要加2，一遍遍試出來的……
j = next1[j];//再重新整理j的值，好找下一個，因為最後一個數的next值肯定為0，是以賦它
}
}
}
下面是一到洛谷的KMP模闆題
題意大概是這樣的：給你兩個字元串s1，s2.
讓你按從小到大的順序輸出s2在s1中的位置
在輸出一行整數，第i個整數代表s2的長度為i的字首的最長長度（其實就是讓你列印next數組的值）
下面是AC碼
#include<bits/stdc++.h>
using namespace std;
int next1[1000005];
string s, ss;
int n, m;
void getnext()
{
int j, k;
j = 0;
k = -1;
next1[0] = -1;
while(j < m)
{
if(k == -1 || ss[j] == ss[k])
next1[++j] = ++k;
else
k = next1[k];
}
}
void kmp()
{
int i = 0;
int j = 0;
getnext();
for(int i = 0; i < n; i++)
{
while(j > 0 && s[i] != ss[j])
j = next1[j];
if(s[i] == ss[j])
j++;
if(j == m)
{
cout<<i - m + 2 <<'\n';
j = next1[j];
}
}
}
int main()
{
cin>>s>>ss;
n = s.size();
m = ss. size();
kmp();
for(int i = 1; i <= m; i++)
{
cout<<next1[i]<<' ';
}
return 0;
}
代碼的解釋都在上面寫了
KMP的簡單應用：
J - 剪花布條
題意：
給了兩個字元串a，b。讓你輸出a中有幾個完整的b
思路：
可以用KMP算法統計，也可以直接用find函數找，然後找到了就可以把這之前的所有字元删除
#include <bits/stdc++.h>
using namespace std;
int next1[1000005];
string s, ss;
int n, m, ans ;
void getnext()
{
int j, k;
j = 0;
k = -1;
next1[0] = -1;
while(j < m)
{
if(k == -1 || ss[j] == ss[k])
next1[++j] = ++k;
else
k = next1[k];
}
}
int kmp()
{
ans = 0;//用來記錄出現幾次
int i = 0;//i是用來記錄被搜字元串的位置
int j = 0;//j是用來記錄要搜的字元串的位置
getnext();
while(i <= n && j <= m)
{
if(j == m)//找到了一次s2，就讓ans++
{
ans ++;
j = 0;
continue;
}
if(j == -1 || s[i] == ss[j])//i與j處字元比對成功
{
i++;
j++;
}
else//比對不成功就利用next數組來跳躍
j = next1[j];
}
return ans;
}
int main()
{
while(cin>>s)
{
if(s[0] == '#')
break;
else
{
cin>>ss;
n = s.size();
m = ss. size();
cout<<kmp()<<endl;
}
}
return 0;
}
來自作者最真誠的吐槽
之前也學了一遍KMP，但是沒靜下心來去了解，就當做闆子直接套（也不知道為什麼，我明明記得我在oj上面做了一個KMP的題，還wa了，清清楚楚的，但是現在就是找不到，難道我活在夢裡？？！！），現在真正了解了，才知道他有多神奇多牛。還有那個洛谷的題，千萬記得寫函數用int時，得加傳回值，不然就會RE，淦！（你說這直接用void他不香嘛）我差點到死都不知道哪裡錯了，還好有ycgg告訴我了。
昨天下午學了個markdown，晚上又學KMP，從六點在集訓室，到回宿舍繼續幹，一直幹到了零點多，今天上午可算是在圖書館用markdown語言寫出來了這篇KMP算法的博文，屬實不容易……
不得不說，typora真滴好用，太喜歡這種簡約的風格了，吹爆typora……
（好奇怪啊，我導入到csdn的時候，外部的照片就會丢失，果然得去設定一下typora的圖檔的存儲……）