KMP最小循环节、循环周期：
定理：假设S的长度为len则S存在最小循环节，对S构造next数组，循环节的长度L为len-next[len]，子串为S[0…len-next[len]-1]。
（1）如果len可以被len - next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T = len/L。
（2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L = L-(len-L)%L = L-next[len]%L，L = len-next[len]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
namespace KMP{
int next[10010];
// 处理模式串的next数组,x[i-next[i]...i-1] == x[0....next[i]-1]
void kmp_pre(char x[], int m, int _next[]){
int i, j;
j = _next[0] = -1;
i = 0;
while(i < m){
while(-1 != j && x[i] != x[j]) j = _next[j];
_next[++i] = ++j;
}
}
// 改进next数组,减少回溯次数，但不能使用next的性质
void kmp_pre_2(char x[], int m, int fast_next[]){
int i, j;
j = fast_next[0] = -1;
i = 0;
while(i < m){
while(-1 != j && x[i] != x[j]) j = fast_next[j];
if(x[++i] == x[++j]) fast_next[i] = fast_next[j];
else fast_next[i] = j;
}
}
//模式匹配,返回出现次数，x模式串，y主串
int kmp(char x[], int m, char y[], int n){
int i, j;
int ans = 0;
kmp_pre(x, m, next);
//kmp_pre_2(x, m, next);
i = j = 0;
while(i < n){
while(-1 !=j && y[i] != x[j]) j = next[j];
i++; j++;
if(j >= m){
ans++;
//i-m即为模式串在主串中的开始位置
j = next[j];
}
}
return ans;
}
}
|
hdu3336 next数组+dp
大意：给你个字符串如abab，它的子串a，ab，aba，abab出现次数
即2+2+1+1=6
dp[i]表示以第i个字符结尾的子串出现次数
dp[i] = dp[next[i]] + 1
对于abab，next[]={-1,0,0,1,2}
当i=1时，表示子串a，dp[1] = dp[next[1]] + 1 = dp[0] + 1 = 1，‘a’
当i=2时，表示子串ab，dp[2] = dp[next[2]] + 1 = dp[0] + 1 = 1，‘ab’
当i=3时，表示子串aba，dp[3] = dp[next[3]] + 1 = dp[1] + 1 = 2，‘a’,‘aba’
当i=4时，表示子串abab，dp[4] = dp[next[4]] + 1 = dp[2] + 1 = 2，‘ab’,‘abab’
以a结尾的有’a',‘a’,‘aba’;
以b结尾的有’ab',‘ab’,‘abab’;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <stdio.h>
#include <string.h>
#define mem(x,y) memset(x,y,sizeof(x))
const int mod = 10007;
namespace KMP{
int next[200001];
// 处理模式串的next数组,x[i-next[i]...i-1] == x[0....next[i]-1]
void kmp_pre(char x[], int m, int _next[]){
int i, j;
j = _next[0] = -1;
i = 0;
while(i < m){
while(-1 != j && x[i] != x[j]) j = _next[j];
_next[++i] = ++j;
}
}
}
int t,n;//200000
char str[200001];
int dp[200001];
int main(){
scanf("%d",&t);
while(t--){
mem(KMP::next,0);
scanf("%d",&n);
scanf("%s",str);
KMP::kmp_pre(str,n,KMP::next);
int ans=0;
mem(dp,0);
for(int i=1;i<=n;i++){
dp[i] = (dp[KMP::next[i]]+1)%mod;
ans = (ans + dp[i])%mod;
}
printf("%d\n",ans );
}
return 0;
}
|