KMP

例：在a串中查找b串的位置。（len <= 1e6）

O(n2)的暴力是好想的。两层循环，第一层遍历a串，第二层遍历b串，对应比较即可。

但我们会发现对于a串，我们每次都不断将循环变量i右移，可匹配失败后，又将i返回至右移之前的位置。

太劣了，所以我们选择取消i的返回操作，每次用b串去匹配a串。

但当b失配时，我们不能直接将b串循环变量归零，否则会有遗漏。

对于b串的适配位置j，b[1……j-1]都已匹配成功，此时我们选择断臂自救。

将j左移，直至b[1……j]再次与a串匹配成功，显然匹配成功的子串变小了。

这就是我们要找的最长公共前后缀。用kmp[i]表示b[1……i]的最长公共前后缀。

lb = strlen(b + 1);
int j = 0;
for(int i = 2; i <= lb; i++){
    while(j && b[j + 1] != b[i]) j = kmp[j];
    if(b[j + 1] == b[i]) j++;
    kmp[i] = j;    
}