前缀函数
计算前缀函数的朴素算法
- 在一个循环中以i=1->n-1的顺序计算前缀函数π[i]的值（π[0]被赋值为0）。
- 为了计算当前的前缀函数值π[i]，我们令变量j从最大的真前缀长度i开始尝试。
- 如果当前长度下真前缀和真后缀相等，则此时长度为π[i]，否则令j自3减1，继续匹配，直到j=0。
- 如果j=0并且仍没有任何一次匹配，则置π[i]=0并移至下一个下标i+1。
1
2
3
4
5
6
7
8
9
10
11
12
13
| static int[] prefix_function(String s){
int n=s.length();
int[] pi=new int[n];
for(int i=1;i<n;i++){
for(int j=i;j>=0;j--){
if(s.substring(0,j).equals(s.substring(i-j+1,i+1))){
pi[i]=j;
break;
}
}
}
return pi;
}
|
时间复杂度O(N^3)
计算前缀函数的高效算法
有上一段代码可知，相邻的前缀函数值至多增加1.
当取一个尽可能大的π[i+1]时，必然要求新增的s[i+1}也与之对应的字符匹配，即s[i+1]=s[π[i]]，此时π[i+1]=π[i]+1[i]+1。
1
2
3
4
5
6
7
8
9
10
11
12
| static int[] prefix_function(String s){
int n=s.length();
int[[] pi=new int[n];
for(int i=1;i<n;i++){
for(int j=pi[i-1]+1;j>=0;j--){
if(s.substring(0,j).equals(s.substring(i-j+1,i+1))){
pi[i]=j;
break;
}
}
}
}
|
时间复杂度O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| static int[] prefix_function(String s){
int n=s.length();
int[] pi=new int[n];
for(int i=1;i<n;i++){
int j=pi[i-1];
while(j>0&&s.charAt(i)!=s.charAt(j)){
j=pi[j-1];
}
if(s.charAt(i)==s.charAt(j)){
j++;
}
pi[i]=j;
}
return pi;
}
|
时间复杂度 O（n）。
在字符串中查找子串（KMP算法）
给定一个文本t和一个字符串s，我们尝试找到并展示s在t中的所有出现。
为了简便起见，我们用n表示字符串s的长度，用m表示文本t的长度。
我们构造一个字符串s+#+t，其中#为一个既不出现在s中也不出现在t中的分隔符。接下来计算该字符串的前缀函数。现在考虑该前缀函数除去最开始n+1,个值（属于s和分隔符的函数值）后其余函数值的意义。根据定义，π[i]为右端点在i且同时为一个前缀的最长真子串的长度，具体到我们的这种情况下，其值为与s的前缀相同且右端点位于i的最长子串的长度。由于分隔符的存在，该长度不可能超过n。而如果等式π[i]=n成立，则意味着s完整出现在该位置（即右端点位于位置i）。注意该位置的下标是对字符串s+#+t而言的。
因此如果在某一位置i有π[i]=n成立，则字符串s在字符串t的i-(n-1)-(n+1)=i-2n处出现。
1
2
3
4
5
6
7
8
9
10
11
12
| static List<Integer> find_occurrences(String text,String pattern){
String cur=pattern + '#' +text;
int sz1=text.length(),sz2=pattern.length();
List<Integer> v=new ArrayList<>();
int[] lps=prefix_function(cur);
for(int i=sz2+1;i<=sz1+sz2;i++){
if(lps[i]=sz2){
v.add(i-2*sz2);
}
}
return v;
}
|
时间复杂度：O（n+m）
空间复杂度：O（n）
字符串的周期
对于字符串s和0<p<=|s|,若s[i]=s[i+p]对所有i属于[0,|s|-p-1]成立，则称p是s的周期。
对于字符串s和0<=r<|s|，若s长度为r的前缀和长度为r的后缀相等，就称s长度wwr的前缀是s的border。
由s有长度为r的border可以推导出|s|-r是s的周期。
根据前缀函数的定义，可以得到s所有的border长度，即π[-1],π[π[m-1]-1],…。
所以根据前缀函数可以在O（n）的时间内计算出s所有的周期。其中，由于π[n-1]是s最长border的长度，所以n-π [n-1]是s的最小周期。
统计每个前缀的出现次数