目录

kmp

求模式串在目标串中出现的次数和位置

next数组的一些性质

KMP最小循环节、循环周期:

定理:假设S的长度为len则S存在最小循环节,对S构造next数组,循环节的长度Llen-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]%LL = 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,它的子串aababaabab出现次数

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