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