KMP算法模板

概述

模板出自kuangbin的博客

典型应用:

给你两个字符串,寻找其中一个字符串是否包含另一个字符串,如果包含,返回包含的起始位置。

(1) 头文件

1
2
3
4
5
6
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int Next[N];
char S[N],T[N]; // S:主串 T:模式串
int slen,tlen;

(2) getNext()函数

1
2
3
4
5
6
7
8
9
10
11
12
void getNext()
{
int j,k;
j = 0; k = -1; Next[0] = -1;
while(j < tlen)
{
if(k == -1 || T[j] == T[k])
Next[++j] = ++k;
else
k = Next[k];
}
}

(3) 返回模式串T在主串S中首次出现的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 返回模式串T在主串S中首次出现的位置
// 返回的位置是从0开始的
int KMP_Index()
{
int i = 0,j = 0;
getNext();

while(i < slen && j < tlen)
{
if(j == -1 || S[i] == T[j])
{
i++; j++;
}
else
j = Next[j];
}
if(j == tlen)
return i-tlen;
else
return -1;
}

(4) 返回模式串在主串S中出现的次数

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
int KMP_Count()
{
int ans = 0;
int i,j = 0;

if(slen == 1 && tlen == 1)
{
if(S[0] == T[0])
return 1;
else
return 0;
}
getNext();
for(i = 0;i < slen;i++)
{
while(j > 0 && S[i] != T[j])
j = Next[j];
if(S[i] == T[j])
j++;
if(j == tlen)
{
ans++;
j = Next[j];
}
}
return ans;
}

(5) 全家福

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
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;

/***************KMP***************/
const int N = 1e5+10;
int Next[N];
char S[N],T[N]; // S:主串 T:模式串
int slen,tlen;

void getNext()
{
int j,k;
j = 0; k = -1; Next[0] = -1;
while(j < tlen)
{
if(k == -1 || T[j] == T[k])
Next[++j] = ++k;
else
k = Next[k];
}
}

// 返回模式串T在主串S中首次出现的位置
// 返回的位置是从0开始的
int KMP_Index()
{
int i = 0,j = 0;
getNext();

while(i < slen && j < tlen)
{
if(j == -1 && S[i] == T[j])
{
i++; j++;
}
else
j = Next[j];
}
if(j == tlen)
return i-tlen;
else
return -1;
}

// 返回模式串在主串S中出现的次数
int KMP_Count()
{
int ans = 0;
int i,j = 0;

if(slen == 1 && tlen == 1)
{
if(S[0] == T[0])
return 1;
else
return 0;
}
getNext();
for(i = 0;i < slen;i++)
{
while(j > 0 && S[i] != T[j])
j = Next[j];
if(S[i] == T[j])
j++;
if(j == tlen)
{
ans++;
j = Next[j];
}
}
return ans;
}
/***************END***************/

int main()
{
int TT;
cin >> TT;
while(TT--)
{
cin >> S >> T;
slen = strlen(S);
tlen = strlen(T);
cout << "模式串T在主串中首次出现的位置是: " << KMP_Index() << endl;
cout << "模式串T在主串S中出现的次数为: " << KMP_Count() << endl;
}
return 0;
}

(6) 补充

KMP的优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void getNext()
{
int j,k;
j = 0,k = -1,Next[0] = -1;
while(j < tlen)
{
if(k == -1 || T[j] == T[k])
{
j++,k++;
if(T[j] == T[k])
Next[j] = Next[k]; // 直接走到下一个不相等的地方
else
Next[j] = k;
}
else
k = Next[k];
}
}

Next[]数组求循环节
性质:

  • len-next[i]为此字符串的最小循环节(i为字符串的结尾)
  • 另外如果len%(len-next[i])==0,此字符串的最小周期就为len/(len-next[i])
  • 如果len%(len-next[i]) != 0 则没有循环节???(小声逼逼)

相关习题:

HDU3746 Cyclic Nacklace
HDU1358 Period
POJ2406 Power Strings