kmp算法

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

int KMP(char * t, char * p)
{
int i = 0;
int j = 0;
while (i < strlen(t) && j < strlen(p))
{
if (j == -1 || t[i] == p[j])
{
i++;
j++;
}
else
j = next[j];//比如第一篇里的ababababca
// abababca
//手算：i=6,j=6，哦吼，不一样，next[i]为模式串0~i-1位的最长公共子串，有
//m=4，abab,那么要从哪里开始比较起来，j=m(即第5个开始）
if (j == strlen(p))
return i - j;
else
return -1;
}
void getNext(char * p, int * next)
{
next[0] = -1;
int i = 0, j = -1;
while (i < strlen(p))
{
if (j == -1 || p[i] == p[j])
{
++i;
++j;
next[i] = j;
}
else
j = next[j];如abaabcac，next[]{-1,0,-1,1,1,2,0,1};//咋算呢，
//next[0]是-1，没啥意义，next[k]，0-k-1最长公共子串的个数，不信算一哈，再跑一会程序验证
}
}
}
------------------------------------------------------------------------------
https://blog.csdn.net/czw8528/article/details/23935153
getNextval
void getnextval(char p[])
{
nextval[0]=-1;
int i=0,j=-1,lenp=strlen(p);
while(i!=lenp-1)
{
if(j==-1||p[i]==p[j])
{
++i;
++j;
if(p[i]!=p[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/***严蔚敏版的数据结构***/
/***字符串匹配算法***/
/**这个只是把下标换成从1开始罢了**/
#include<cstring>
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MAXSTRLEN 255
//用户可在255以内定义最长串长
typedef char SString[MAXSTRLEN+1];
//0号单元存放串的长度
Status StrAssign(SString T, char *chars) { //生成一个其值等于chars的串T
int i;
if (strlen(chars) > MAXSTRLEN)
return ERROR;
else {
T[0] = strlen(chars);
for (i = 1; i <= T[0]; i++)
T[i] = *(chars + i - 1);//傻眼了吧，*char表示的是指针char指向的字符,chars++，表示指针后移
return OK;
}
}
//算法4.3　计算next函数值
void get_next(SString T, int next[])
{ //求模式串T的next函数值并存入数组next
int i = 1, j = 0;
next[1] = 0;
while (i < T[0])
if (j == 0 || T[i] == T[j])
{
++i;
++j;
next[i] = j;
}
else
j = next[j];
}//get_next
//算法4.2　KMP算法
int Index_KMP(SString S, SString T, int pos, int next[])
{
// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
//其中，T非空，1≤pos≤StrLength(S)
int i = pos, j = 1;
while (i <= S[0] && j <= T[0])
if (j == 0 || S[i] == T[j]) // 继续比较后继字
{
++i;
++j;
}
else
j = next[j]; // 模式串向右移动
if (j > T[0]) // 匹配成功
return i - T[0];
else
return 0;
}//Index_KMP
int main()
{
SString S;
StrAssign(S,"aaabbaba") ;
SString T;
StrAssign(T,"abb") ;
int *p = new int[T[0]+1]; // 生成T的next数组
get_next(T,p);
cout<<"主串和子串在第"<<Index_KMP(S,T,1,p)<<"个字符处首次匹配n";
return 0;
}