【模板】【字符串】KMP算法

字符串

字符串匹配的基础算法KMP 时间复杂度O（m+n）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int kmp(char s1[105],char s2[105]){
	int i=0,j=next[0]=-1;
	int len1=strlen(s1),len2=strlen(s2);
	while (i<len2-1){
		if (j<0 || s2[i]==s2[j])
			next[++i]=++j;
		else
			j=next[j];
	}
	
	i=0,j=0;
	while (i<len1 && j<len2){
		if (j<0 || s1[i]==s2[j]) i++,j++;
		else j=next[j];
	}
	
	if (j==len2) return i-j;
	return -1;
}