一些定義：
1. Border: 如果一個字符串的某個前綴同與它長度相同的后綴完全相同，就稱這個前綴（后綴）是這個字符串的一個Border.
2. 周期:如果一個字符串s滿足對于任意的p < i \(\leqslant\) |s|, s[i] = s[i - p], 則稱p是字符串s的周期，一個字符串可能有很多個周期。
3. 循環(huán)節(jié)：在周期的概念中，字符串末尾可能有未盡的循環(huán)單元，但是在循環(huán)節(jié)的概念中，必須每個循環(huán)單元都是完整的，即p | \(\lvert s \rvert\)(p整除字符串的長度)，循環(huán)節(jié)是每個循環(huán)單元的長度。

重要性質(zhì)：
1. 如果p是s的周期， 那么[1, |s| - p]是s的一個Border
證明: p是s的周期，那么s[i] = s[i + p];
[1, q]是s的一個Border, 那么s[1] = s[|s| - q + 1], s[2] = s[|s| - q + 2] \(\dots\) s[q] = s[|s|];
就是說 |s| - q + i = i + p => q = |s| - p;
這樣的話，求周期和求Border的問題就可以相互轉(zhuǎn)化。
2. s的Border的Border也是s的Border;
證明：稍微想一下就行了。

Border的求法:
要求所有的Border，只要求出所有前綴的最大Border就可以了。
設(shè)next[i] = prefix[i]的最大非平凡Border
很明顯,next[1] = 0;
然后，考慮所有prefix[i]所有長度不為1的Border，任意一個，在減去一個字符以后都會是prefix[i - 1]的前綴。
那么我們在求prefix[i]的最大Border的時候，就依次看next[i - 1], next[next[i - 1]]..0， 檢查后一個字符是否相等；
時間復雜度O(n)，用勢能分析法可以估算出來。

CODE:

void init(string & s) {
	nxt[1] = 0;
	for(int i = 2; i <= s.size() - 1; i ++) {
		nxt[i] = nxt[i - 1];
		while(nxt[i] && s[nxt[i] + 1] != s[i]) nxt[i] = nxt[nxt[i]];
		nxt[i] += (s[i] == s[nxt[i] + 1]);
	}
}

KMP:
首先貼一個樸素版本的代碼

bool brute(string & s1, string & s2) {
	int n = s1.size() - 1;
	int m = s2.size() - 1;
	bool vis;
	for(int i = 1;  i <= n - m + 1; i ++) {
		vis = true;
		for(int j = 1; j <= m; j ++) {
			if(s2[j] != s1[i + j - 1]) vis = false;
		}
		if(vis) return true;
	}
	return false;
}

可以看到，在每次匹配失敗以后，i指針只會后移一位，這太蠢了。
我們可以每次移動一個更合理的距離。
不太好說，可以找網(wǎng)上很經(jīng)典的圖，總之是枚舉nxt[j],nxt[nxt[j]]就可以了。