KMP算法

简单的匹配算法并不蠢

S串的指针回跳，接下来就相当于P串自己跟自己比

不用知道S串的全貌就能知道j指针跳到哪——预处理

手算next数组怎么算

先规定一下next数组存的是什么：如果P串的第x个元素与S串的不匹配，回退到P的第next[x]个元素，继续比。

那么next[1]是没有意义的（第一个元素都不一样，只好进入新一轮比较）
next[x]的值有什么特点？P串x之前的这个串，头=尾，这个相等的情况具体多长，就是next[x]的值（再加一，因为我们要的是新位置，前k个能自匹配，新位置就是k+1）

做个练习

a b a b a b c a b a b a b c d a b c
  1 1 2 3 4 5 1 2 3 4 5 6 7 8 1 2 3
1
2

先不管next数组的算法（ 假设next数组有了）KMP算法如何写呢

S串的指针i不回退
情况① S[i] == P[j]
否则：如果j==1,j已经回退到P的第一个字符了，还匹配不上。那么S[i]这趟就结束了，i++，j=1，下一趟重新开始。
如果还没退到P的头，那j=next[j]即可

	while (i <= n)
	{
		if (j == 0)
			i++; j=1;

		if (S[i] == P[j])
		{
			i++; j++;
			if (j > m) return S + j - 1;
		}
		else
		{
			j = next[j];
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最后的问题：计算机怎么算next数组：递推——假设知道了next[i],next[i+1]如何计算？

void findNext(char * P)
{
	int n = strlen(P) -1;
	int i = 1, j = 0;
	next[1] = 0;// next[1]本身没有意义
	while (i < n)
	{
		//递推，已经知道了next[i],推出next[i+1]是几
		if (j == 0)
		{
			next[i + 1] = 1;
			i++;
			j = 1;
		}
		if (P[i] == P[j])
		{
			/*if (P[i + 1] == P[j + 1])
				next[i + 1] = next[next[j + 1]];
			else*/
				next[i + 1] = j + 1;
			i++; j++;
		}
		else
		{
			j = next[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

浙大数据结构编程题34：KMP 串的模式匹配

# include 
# include 
# define N 1000010

int next[N];

void findNext(char * P)
{
	int n = strlen(P) -1;
	int i = 1, j = 0;
	next[1] = 0;// next[1]本身没有意义
	while (i < n)
	{
		//递推，已经知道了next[i],推出next[i+1]是几
		if (j == 0)
		{
			next[i + 1] = 1;
			i++;
			j = 1;
		}
		if (P[i] == P[j])
		{
			if (P[i + 1] == P[j + 1])
				next[i + 1] = next[next[j + 1]];
			else
				next[i + 1] = j + 1;
			i++; j++;
		}
		else
		{
			j = next[j];
		}
	}
}

char * KMP(char * S, char * P)
{
	findNext(P);
	// S,P从下标为1开始存
	int n = strlen(S)-1;
	int m = strlen(P)-1;
	int i = 0, j = 0;
	while (i <= n)
	{
		if (j == 0)
		{
			i++; j=1;
		}

		if (S[i] == P[j])
		{
			i++; j++;
			if (j > m) return S + i - j + 1;
		}
		else
		{
			j = next[j];
		}
	}
	return NULL;
}

int main(void)
{
	char S[N], P[N];
    S[0] = P[0] = 1;
	scanf("%s", S + 1);
    int n;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%s", P+1);
        char * ans = KMP(S, P);
	    if (ans) 
            printf("%s\n", ans);
	    else
		    printf("Not Found\n");
    }

	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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

the end

给自己留一个填空题，没事多填填୧⍤⃝

# include 
# include 
# define N 1000010

char S[N], P[N];
int n, m; //n是S的实际长度，m是P的实际长度
int next[N];

void findNext(char * P)
{
	
}

char * KMP(char * S, char * P)
{
	findNext(P);
	
}

int main(void)
{
	
	scanf("%s%s", S + 1, P + 1);
	int n = strlen(S) - 1;
	int m = strlen(P) - 1;

	char * ans = KMP(S, P);
	if (ans) 
		printf("%s\n", ans);
	else
		printf("Not Found\n");

	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