三, KMP && EXKMP

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
int KMP(char *s,char *p)
{
	int i=0;
	int j=0;
	int lens=strlen(s);
	int lenp=strlen(p);
	while(i<lens&&j<lenp)
	{
		//如果j=-1(表示第一次开始或者重新开始匹配)，即失配于首字符
		if(j==-1||s[i]==p[j])
		{
			j++;
			i++;
		}
		else
		{
			//如果j!+-1,或者当前匹配失败 ，则 
			j=nextt[j]; // i不变，j=next[j] 
		}
	}
	if(j==lenp)
	return 1;//匹配成功 
	else
	return 0; 
}
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
//扩展KMP可求问题：给出一个长为N的字符串S，再给出一个长为M的字符串T
//求S的所有后缀中和T的最长公共前缀
//假设s为文本串(长度为n),T为模式串(长度为m)
char s[N], T[N];
int n, m;
int Next[N];    //Next[i]代表T[i~m-1]与T[0~m-1]最长公共前缀
int ex[N];      //extend数组,代表s[i~n-1]与T[0~m-1]最长公共前缀
                //注意到，如果有一个位置extend[i]=m,则表示T在S中出现，而且是在位置i出现，这就是标准的KMP问题
void Get_Next() {
    Next[0] = m;
    int j = 0;
    while (j + 1 < m && T[j] == T[j + 1])  //计算Next[1]
        j++;
    Next[1] = j
    int po = 1;    //设po为答案伸得最远的后缀的下标
    for (int i = 2; i < m; i++) 
        int p = Next[po] + po - 1; //已匹配最大位置
        int L = Next[i - po];        //前缀长度
        if (i + L < p + 1)
            Next[i] = L;
        else {
            j = max(0, p - i + 1);
            while (i + j < m && T[i + j] == T[j])
                j++;
            Next[i] = j;
            po = i;
        }
    }
}

void EX_KMP() {
    Get_Next();
    int j = 0;
    while (j < n && j < m && s[j] == T[j])
        j++;
    ex[0] = j;
    int po = 0;
    for (int i = 1; i < n; i++) {
        int p = ex[po] + po - 1;
        int L = Next[i - po];
        if (i + L < p + 1)
            ex[i] = L;
        else {
            j = max(0, p - i + 1);
            while (i + j < n && j < m && s[i + j] == T[j])
                j++;
            ex[i] = j;
            po = i;
        }
    }
}