前言：前段时间在写pta上面的代码题时遇到一个查找字符串字串的问题，一开始采取i，j循环遍历的方法暴力寻找，但是很可惜时间复杂度上出现问题，于是经过学习，初步尝试运用kmp算法来解决查找字符串字串中时间复杂度的问题。
对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
63
64
65
| #include <stdio.h>
#include <string.h>
#include<stdlib.h>
void computeLPSArray(char* pat, int M, int* lps) {
int len = 0,i=1;
lps[0] = 0;
while (i < M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0)
{
len = lps[len - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
}
void KMPSearch(char* pat, char* txt) {
int M = strlen(pat);
int N = strlen(txt);
int* lps = (int*)malloc(M * sizeof(int));
computeLPSArray(pat, M, lps);
int i = 0;
int j = 0;
while (i < N)
{
if (pat[j] == txt[i])
{
i++;
j++;
}
if (j == M)
{
printf("找到模式字符串 '%s' 的起始位置: %d\n", pat, i - j);
j = lps[j - 1];
}
else if(i < N && pat[j] != txt[i])
{
if (j != 0)
{
j = lps[j - 1];
} else
{
i++;
}
}
}
}
int main(){
char txt[] = "ABABDABACDABABCABAB";
char pat[] = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}
|
个人理解，掌握kmp算法的关键就是掌握lps数组的构造（网上大部分也称next数组，就把lps换成next），lps数组也就是找字串中的最大公共前后缀，它可以帮助我们查找子串时优化“回溯”过程，因为用i，j单纯暴力循环每次都要回到最初会有很多浪费，利用lps数组的构造就可以优化这个过程。具体概念理解，以及构造思路还需要在网络上自己找视频理解。
接下来是pta里面的一道题，运用kmp算法解决。
7-11 删除字符串中的子串
分数 10
作者 白洪欢
单位 浙江大学
输入2个字符串S1和S2，要求删除字符串S1中出现的所有子串S2，即结果字符串中不能包含S2。
输入格式：
输入在2行中分别给出不超过80个字符长度的、以回车结束的2个非空字符串，对应S1和S2。
输出格式：
在一行中输出删除字符串S1中出现的所有子串S2后的结果字符串。
输入样例：
1
2
| Tomcat is a male ccatat
cat
|
输出样例：
下面是通过代码
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
| #include <stdio.h>
#include <string.h>
#include <stdlib.h>
void computeLPSArray(char* pat, int M, int* lps) {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
void KMPSearchAndDelete(char* txt, char* pat) {
int M = strlen(pat);
int N = strlen(txt);
int* lps = (int*)malloc(M * sizeof(int));
computeLPSArray(pat, M, lps);
int i = 0;
int j = 0;
while (i < N) {
if (pat[j] == txt[i]) {
i++;
j++;
}
if (j == M) {
memmove(&txt[i - j], &txt[i], N - i + 1);
N -= j;
txt[N] = '\0';
j = 0;
i = 0;
} else if (i < N && pat[j] != txt[i]) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
free(lps);
}
int main() {
char s1[256];
char s2[81];
fgets(s1, sizeof(s1), stdin);
s1[strcspn(s1, "\n")] = 0;
fgets(s2, sizeof(s2), stdin);
s2[strcspn(s2, "\n")] = 0;
while (strstr(s1, s2) != NULL) {
KMPSearchAndDelete(s1, s2);
}
printf("%s\n", s1);
return 0;
}
|
