KMP和Z函數(shù)，首先要先了解什么是KMP，把KMP了解了，使用Z函數(shù)就能更加順手。很多人初次接觸KMP的時(shí)候，思路很容易混亂，導(dǎo)致寫出來(lái)的程序也很混亂。

Knuth-Morris-Pratt字符串查找算法，簡(jiǎn)稱為 “KMP算法”，常用于在一個(gè)文本串S內(nèi)查找一個(gè)模式串P的出現(xiàn)位置，這個(gè)算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年聯(lián)合發(fā)表，故取這3人的姓氏命名此算法。

KMP可以解決問(wèn)題類型：

（1）前綴函數(shù)：查找子串，每個(gè)前綴的出現(xiàn)次數(shù)，本質(zhì)不同子串的個(gè)數(shù)O(n^2)，字符串壓縮：找到t使得s可以被多個(gè)t重復(fù)出現(xiàn)得到

（2）前綴自動(dòng)機(jī)

舉例說(shuō)明：如果有兩個(gè)字符串，問(wèn)：如何快速在一串序列中，找出目標(biāo)串。

相信很多人拿到題的第一時(shí)間就優(yōu)先想到了暴力破解（用兩個(gè)指針，開始時(shí)分別指向兩個(gè)串的開頭，然后比較，如果相同繼續(xù)掃描下一個(gè)字符，一旦出現(xiàn)不相同，兩個(gè)指針進(jìn)行回溯，主串的指針回溯到下一位，目標(biāo)串的指針回溯至第一位，然后繼續(xù)按照上述步驟比較）

如圖所示

上面的這種暴力匹配是可行的，但是時(shí)間復(fù)雜度一看就很高，暴力匹配的缺陷所在——回溯太過(guò)頻繁了。只要出現(xiàn)不匹配就需要回溯到下一位。而KMP算法是為了解決 “如何在主串中快速找到目標(biāo)串”而孕育出來(lái)的算法。

讓我們用KMP算法來(lái)解答這個(gè)問(wèn)題吧，如圖：

無(wú)腦回溯并不合理，比如下面這種情況中，如果讓你進(jìn)行回溯的話，你肯定不會(huì)直接回溯到下一位，這是因?yàn)槟忝靼字苯踊厮莸较乱晃粫?huì)導(dǎo)致連第一位都不會(huì)匹配，就更別談后面了

KMP的算法的核心點(diǎn)就在這里：不要回溯到無(wú)效的地方，讓其回溯到有效的位置

Z函數(shù)可以解決問(wèn)題的類型有：查找子串，本質(zhì)不同子串的個(gè)數(shù)O(n^2)，字符串壓縮。

定義：前綴函數(shù)π(prefix function): π[i]代表子串s[0…i]與其后綴相等的最長(zhǎng)真前綴。

O（n）,在線

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;
}

Z函數(shù)：z[i]代表串s和其后綴s[i . . . n?1]的LCP，定義z[0]=0

O（n）

vector<int> z_function(string s) {
	int n = (int) s.length();
	vector<int> z(n);
	for (int i = 1, l = 0, r = 0; i < n; ++i) {
		if (i <= r)
			z[i] = min (r - i + 1, z[i - l]);
		while (i + z[i] < n && s[z[i]] == s[i + z[i]])
			++z[i];
		if (i + z[i] - 1 > r)
			l = i, r = i + z[i] - 1;
	}
	return z;
}

關(guān)于在KMP與Z函數(shù)中，我們還是需要做大量的題，才能更好的運(yùn)用。