KMP算法與前綴函數(shù)

（一）前綴函數(shù)

一個(gè)字符串s的border是一個(gè)最長的字符串，且既是s的后綴，又是s的真前綴。

給定長為n的字符串s，其前綴函數(shù)定義為一個(gè)長為n的數(shù)組π。其中π[i]為s的第i個(gè)前綴的border長度。

（二）KMP算法

全稱為 Knuth-Morris-Pratt 算法，是由 Knuth, Morris 和 Pratt 這三個(gè)人創(chuàng)造的算法，可以在O(n+m)的時(shí)間內(nèi)使用 O(n) 的空間完成如下的任務(wù)：

給定一個(gè)字符串S和一個(gè)模式串T ，求出S在T中所有出現(xiàn)的位置。

其中 |S| = n， |T| = m。

KMP算法主要依賴的是“Next函數(shù)”這個(gè)東西。

（1）Next函數(shù)

Next函數(shù)，有時(shí)候也被稱作 “前綴函數(shù)”，是KMP算法的核心部分。

我們以一個(gè)數(shù)組 π 來表示它。

其旨在求得任意一個(gè)前綴的border長度。

（2）什么是border？

border指的是一個(gè)字符串內(nèi)，真前綴和真后綴相等的那一部分。

這樣的真前綴和真后綴可能有很多種，我們需要找的是最長的那一組。

真前綴和真后綴說的是前綴和后綴中除去字符串本身之后剩下的部分。

（3）如何求得border？

1. 樸素算法

我們顯然可以暴力掃，最終的復(fù)雜度是。

// C++ Version
vector<int> prefix_function(string s)
{
	int n = ( int )s.length();
	vector<int> pi(n);
	for(int i = 1; i < n; i++)
		for(int j = i; j >= 0; j--)
			if(s.substr(0, j) == s.substr(i - j + 1, j))
			{
				pi[i] = j;
				break;
			}
	return pi;
}

# Python Version
def prefix_function(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		for j in range(i, -1, -1):
			if s[0 : j] == s[i - j + 1 : i + 1]:
				pi[i] = j
				break
	return pi

2. 優(yōu)化

我們會發(fā)現(xiàn)，相鄰的兩個(gè)函數(shù)值最多會增加1。

也就是說，當(dāng)我們移動到下一個(gè)位置時(shí)，Next函數(shù)的值要么增加一，要么維持不變，要么減少。

此時(shí)改進(jìn)的算法如下：

// C++ Version
vector<int> prefix_function(string s)
{
	int n = ( int )s.length();
	vector<int> pi(n);
	for(int i = 1; i < n; i++)
		for(int j = pi[i - 1] + 1; j >= 0; j--)  // improved: j=i => j=pi[i-1]+1
			if(s.substr(0, j) == s.substr(i - j + 1, j))
			{
				pi[i] = j;
				break;
			}
	return pi;
}

# Python Version
def prefix_function(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		for j in range(pi[i - 1] + 1, -1, -1):
			if s[0 : j] == s[i - j + 1 : i + 1]:
				pi[i] = j
				break
	return pi

此時(shí)，我們每一個(gè)前綴最多需要比對O(n)級別的字符串，總復(fù)雜度降到了。

3. 繼續(xù)優(yōu)化

剛才我們只考慮到了的情況，即函數(shù)值增加1。

那么對于其他的情況呢？

我們考慮

在我們之前的想法里面，我們就需要枚舉出來可能的border長度，并與實(shí)際情況進(jìn)行比較。

我們嘗試避免這些無謂的比較。

觀察一下我們想要找到的東西：

我們想要找到兩個(gè)字符串 s [ 0 → j ? 1 ] 和 s [ i ? j + 1 → i ] ，他們完全相等，同時(shí)也分別是 s [ 0 → i ]  的一個(gè)前綴和一個(gè)后綴。

我們發(fā)現(xiàn)，這兩個(gè)字符串是完全包含在 s [ 0 → π [ i ] ? 1 ] 和 s [ i ? π [ i ] + 1 → i ] 這兩個(gè)完全相等的字符串內(nèi)的。

所以，我們就可以將其轉(zhuǎn)化成為尋找字符串 s [ 0 → π [ i ] ? 1 ] 的border。

所以說，我們需要找的就是 s [ 0 → π [ π [ i ] ] ? 1 ] 和 s [ i ? π [ π [ i ] ] + 1 → i ] 。

然后我們嘗試將納入我們當(dāng)前找到的border里面。

如果匹配，那就向前移動；

如果失配，那就繼續(xù)尋找當(dāng)前長度的border，直到最后到達(dá)0。

此時(shí)改進(jìn)的算法如下：

// C++ Version
vector<int> prefix_function(string s)
{
	int n = ( int )s.length();
	vector<int> pi(n);
	for(int i = 1; i < n; i++)
	{
		int j = pi[i - 1];
		while(j > 0 && s[i] != s[j]) j = pi[j - 1];
		if(s[i] == s[j]) j++;
		pi[i] = j;
	}
	return pi;
}

# Python Version
def prefix_function(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j > 0 and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

同時(shí)我們還可以發(fā)現(xiàn)，我們進(jìn)行優(yōu)化過的算法是一個(gè)在線算法。

（4）KMP

現(xiàn)在終于來到了KMP算法的本體部分。

我們考慮根據(jù)題目給定的 S 和 T 兩個(gè)字符串，拼接成一個(gè)新的字符串 S + ? + T ，其中 ? 代表在 S 和 T 中都沒有出現(xiàn)過的分隔符。

我們考慮計(jì)算新字符串 T 部分的Next函數(shù)。

因?yàn)閷τ?T 部分的每一個(gè)位置，其位置所對應(yīng)的前綴絕對包含 S 和分隔符的。

所以，其Next函數(shù)長度絕對不會超過n 。（即 |S|）

同時(shí)，我們保證了只會比對 T 部分的字串，因?yàn)榉指舴某霈F(xiàn)使得包含其的后綴無法與同樣長度的前綴匹配，因?yàn)檫@個(gè)字符不在 S 或 T 中出現(xiàn)過，而假如前綴中也包含了它，也會因?yàn)槲恢貌灰粯佣鵁o法匹配。

所以說，如果在某一個(gè)位置 i 有 π [ i ] = n 成立，那么 S 就會在 T  的 i ? 2 n 處出現(xiàn)。

（三）應(yīng)用

求一個(gè)字符串的周期

我們考慮利用border的性質(zhì)。

如果一個(gè)字符串 s 有長度為 r 的border，那么 ∣ s ∣ ? r 一定是 s 的周期，其長度我們這里記作 p 。

就像這樣：

從這里我們可以得出 s [ 0 → 1 ] = s [ 2 → 3 ] = s [ 4 → 5 ] = s [ 6 → 7 ] ，從而得出 r ? ∣ s ∣ = 2 為 s 的周期。

同時(shí)，如果這個(gè)周期的長度 p 可以被 ∣ s ∣ 整除的話，那么長度為 p 的前綴就是 s 的最小循環(huán)元。