KMP

KMP 是单模匹配算法，即在一个长度为 n 的文本串中查找一个长度为 m 的模式串。

KMP 算法的基础

时间复杂度
在用 KMP 算法时，指向 s 的 i 指针不会回溯，而是一直往下走到底。那么 KMP 是如何让 i 不回溯，只回溯 j 的呢？这就是 KMP 的核心———fail[]数组。当出现失配后，进行下一次匹配时，用fail[]指出 j 的回溯的位置。
注：维护一个最大前缀。
注1：完善，fail 指针要标记到 m+1，在模式串第 m 位也匹配成功后仍然可以在 m+1 位进行回溯。
注2：优化，当 t[i] = t[pos]，fail[i+1] 可以回溯到 pos+1，但当 t[i+1] = t[pos+1]，fail[i+1] 回溯后注定失配，所以可以跳过这种无效回溯 fail[i+1] = fail[pos+1]。
注3：统计，统计模式串在文本串的个数，若在文本串中找到的模式串可以有交集，则当 m 位匹配成功后进行回溯 j = fail[m+1], 若在文本串中找到的模式串不能有交集，则当 m 位匹配成功后直接 j = 1 从头来过。

int fail[maxn]; // 回溯指针
char s[maxn], t[maxn]; // 文本串，模式串

void getfail(char t[]) {
    int pos = 0, i = 1, m = strlen(t+1);
    while(i <= m) {
        if (!pos || t[pos] == t[i]) {
            if (t[++i] != t[++pos]) fail[i] = pos;
            else fail[i] = fail[pos];
            // fail[++i] = ++pos; 
        }
        else pos = fail[pos];
    }
}

int kmp(char s[], char t[]) { // 判断第一次匹配位置
    int n = strlen(s+1), m = strlen(t+1), res = 0;
    for(int i = 1, j = 1; i <= n; ++ i) {
        while(j && s[i] != t[j]) j = fail[j];
        if (++j > m) return i - m + 1;
//        if (++j > m) res ++, j = fail[j]; // 统计匹配个数 （可重叠）
//        if (++j > m) res ++, j = 1; // 统计匹配个数 （不重叠）
    }
    return res;
}

最小循环节

在一个字符串中通过不断循环能得到它的最短前缀子串，就是它的最小循环节。例如，abcabcabc 的最小循环节是 abc, abacdeaba 的最小循环节是 cdeaba。 注：原串可添加字符形成完整循环。

注：图一是没有优化过的（即 fail[++i] = ++pos）的草图，图二是优化过的草图，其本质是第 m+1 位失配后的回溯到最后一个最小循环节的首位（若去掉字符串后面一些字符，回溯的最小循环节的排列顺序可能不同）。

    int len = m + 1 - fail[m+1]; // 最小循环节长度
    if (m % len == 0) printf("YES\n"); // 注意：判断字符串是否能由最小循环节构成

扩展 KMP

时间复杂度
定义母串S，和字串T，设S的长度为n，T的长度为m，求T与S的每一个后缀的最长公共前缀，也就是说，设extend数组,extend[i]表示T与S[i,n]的最长公共前缀，要求出所有extend[i] (1 <= i <= n)。
注：设置一个 po 点，维护已知区域 [po, Next[po]+po)，即维护 po 点。

char s[maxn], t[maxn];
int Next[maxn];   // t[i,m]与t的最长相同前缀长度
int exN[maxn];    // s[i,n]与t的最长相同前缀长度

void getNext(char t[]) {
    int m = Next[1] = strlen(t+1);
    int i = 2, po = 2;
    while(i <= m && t[i] == t[i-1]) ++ i;
    Next[po] = i - po;
    for(i = 3; i <= m; ++ i) {
        if (Next[i-po+1] + i < Next[po] + po) Next[i] = Next[i-po+1];
        else { // 已知区域全部匹配成功
            int j = (Next[po] + po < i) ? 0 : po + Next[po] - i;// i 不在已知区域 j 为 0
            while(i+j <= m && t[j+1] == t[i+j]) ++ j;
            Next[po=i] = j;
        }
    }
}

void exkmp(char s[], char t[]) {
    int n = strlen(s+1);
    int m = strlen(t+1);
    int i = 1, po = 1;
    while(i <= n && i <= m && s[i] == t[i]) ++ i;
    exN[po] = i - po;
    for(i = 2; i <= n; ++ i) {
        if (Next[i-po+1] + i < exN[po] + po) exN[i] = Next[i-po+1];
        else { // 已知区域全部匹配成功
            int j = (exN[po] + po < i) ? 0 : po + exN[po] - i;// i 不在已知区域 j 为 0
            while(i+j <= n && j <= m && t[j+1] == s[i+j]) ++ j;
            exN[po=i] = j;
        }
    }
}