淺談KMP算法

目錄

算法由來（曆史課）

問題引入

解法：

（1）暴力解法

（2）玄學解法

KMP算法：

開始前你必須知道的：

next數組：

思路：

代碼：

KMP算法：

思路：

代碼：

模闆題：

KMP算法是一種快速的比對字元子串位置的算法，其思想對于其他一些算法也有沿用

算法由來（曆史課）

KMP算法是由D.E.Knuth，J.H.Morris和V.R.Pratt同時發現，并且于1977年聯合發表，

是以人們稱它為克努特--莫裡斯--普拉特操作(簡稱KMP算法)。

其中D.E.Knuth是《計算機程式設計藝術》的作者（神犇）

問題引入

由兩個字元串，text和pattern，他們都是以0為其實下标存儲的，現在請你程式設計求出pattern在text中最早出現的下标（開頭位置的）

若沒有出現，則輸出-1

輸入樣例：

一共兩行，分别表示text和pattern

ABACABB

AB

輸出樣例：

一行，表示出現的位置

解法：

（1）暴力解法

這是一種很樸素的配對，枚舉text的下标，若該下标開始的子串與pattern相比相同，則輸出目前指針的位置，否則讓指針後移

相當于模拟pattern後移的過程

代碼如下：

bool check(int pos)
{
    for(int i=pos,j=0;j<m;i++,j++)
        if(text[i]!=pattern[j])
            return false;
    return true;
}
void solve()
{
    //n表示text長度，m表示pattern長度
    int ans=-1;
    for(int i=0;i<n;i++)
        if(check(i))
            ans=i,break;
    cout<<ans<<endl;
}
           

時間複雜度：O(nm)不用說，資料稍微大一點就炸了

（2）玄學解法

請思考：能不能不移動pattern的位置就解決問題？

問題稍難，請認真思考10`15min!

盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯

盯盯盯———————————————————————————————思考線

盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯盯

KMP算法：

開始前你必須知道的：

我們可以将text稱之為文本串，将pattern稱之為模式串。

KMP算法是暴力解法的一種優化（吧）

現在定義一個next數組（為了節約時間以及防止關鍵字報錯（我也不懂怎麼回事），以後請寫作ne或自己起名，本文将統一使用next為數組名）

使得next[i]為i下一步跳躍的下标

那麼應該怎麼跳躍呢？！

next數組：

（關于本小節的正确性，這裡講的可能不好，可以戳我了解一下）

思路：

對于一個pattern串，這當中有Ta的字首和字尾，那麼若暴力解法出現失配（即比較text[i]和pattern[j]不相等的時候），向前跳躍一個位置（失配位置的下标pos前一個，即pos-1，0~pos-1之中與text串公共部分的最長相等前字尾的起始位置）。

下面，讓我們開始找前字尾~

情況一：

有的蒻蒻說了，那麼我如下圖的情況是不是就向後跳一個機關呢？

【字醜勿噴】

此處是在pos=4的位置失配，那麼在4之前即0~3這一段子串中，最大相同前字尾是“ABAB”（一個字元串的最大字首等于最大字尾等于它本身），那麼這裡就是不是真的不跳了？

再次觀察，其實還有一個子前字尾是相同的：“AB”與“AB”。于是乎，這種情況就需要pattern跳躍至字尾“AB”的起始位置

我們用i、k模拟pattern的指針，其中k用于給next數組指派（next[i]=k，不要搞反了）。

情況一：

在pattern[k+1]==pattern[i]的時候，

此時的k就可以向前進一個機關了；

情況二：

在pattern[k+1] != pattern[i]的時候（即下一個不同）

k就要移動至k應該跳躍的位置，向前回溯。

即k=next[k]。

注意next[k]是小于k的，無論k取任何值。

情況三：

如果以上情況都沒有發生那麼更新i的位置就是next[i]=k;

代碼：

void get_next()
{
	next[0]=-1;//在0這個位置不存在任何最大前字尾（情況三）
	int k=-1;
	for(unsigned int i=1;i<pattern.size();i++)
	{
		while(k>-1 && pattern[k+1] != pattern[i])//情況二
			k=next[k];
		if(pattern[k+1]==pattern[i])//情況一
			k++;
		next[i]=k;
	}
}
           

KMP算法：

思路：

大體就已經和next數組的一樣了，下面還是說幾種情況。

（下面變量的含義與講解next時含義一樣）

情況一：

若k>-1，并且失配的時候，那麼就需要向前跳躍至next所訓示的位置

即k=next[k];

情況二：

當pattern[k + 1] == text[i]，

k就向後移動一個機關

情況三：

k已經移動至末端了，就輸出位置

即i-pattern.size()+1

代碼：

void kmp()
{
	int k=-1;
	for(unsigned int i=0;i<text.size();i++)
	{
		while(k>-1 && pattern[k+1]!=text[i])
			k=ne[k];
		if(pattern[k+1]==text[i])
			k++;
		if(k==pattern.size()-1)
		{
			return i-k;
		}
	}
	return -1;
}
           

模闆題：

Luogu 3375

POJ 3461