一些定义:
1. Border: 如果一个字符串的某个前缀同与它长度相同的后缀完全相同,就称这个前缀(后缀)是这个字符串的一个Border.
2. 周期:如果一个字符串s满足对于任意的p < i \(\leqslant\) |s|, s[i] = s[i - p], 则称p是字符串s的周期,一个字符串可能有很多个周期。
3. 循环节:在周期的概念中,字符串末尾可能有未尽的循环单元,但是在循环节的概念中,必须每个循环单元都是完整的,即p | \(\lvert s \rvert\)(p整除字符串的长度),循环节是每个循环单元的长度。
重要性质:
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的问题就可以相互转化。
2. s的Border的Border也是s的Border;
证明:稍微想一下就行了。
Border的求法:
要求所有的Border,只要求出所有前缀的最大Border就可以了。
设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指针只会后移一位,这太蠢了。
我们可以每次移动一个更合理的距离。
不太好说,可以找网上很经典的图,总之是枚举nxt[j],nxt[nxt[j]]就可以了。