第一章 自测&关键词回顾
一个人能走的多远, 不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。——KMP
KMP: _阿岳_
第二章 手撕
①就是定长顺序表, 存char; 和顺序表的实现99%相同; ②相关操作, 不如去把string.h看看
第三章 相关应用
第一节 BF算法
aimS的每个区间, 都要和moduleS全部判断
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
| #include <stdio.h>
#include <string.h>
#define N 1000
void BF(char *aimS, char *moduleS) {
for (int index = 0; index < strlen(aimS); index++) {
for (int i = index, j = 0; j < strlen(moduleS); i++, j++) {
if (aimS[i] != moduleS[j]) break;
if (j == strlen(moduleS) - 1) {
int begin = index;
int end = i ;
printf("%d %d\n", begin, end);
break;
}
}
}
}
int main() {
char aimS[N], moduleS[N];
scanf("%s", aimS);
scanf("%s", moduleS);
BF(aimS, moduleS);
return 0;
}
|
第二节 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
| #include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100
void getNext(int *next, char *moduleS) {
next[0] = -1;
for (int i = 1; i < strlen(moduleS); i++) {
int t = next[i - 1];
while (t != -1 && moduleS[t] != moduleS[i - 1]) { t = next[t]; }
next[i] = t + 1;
}
}
void KMP(int *next, char *aimS, char *moduleS) {
for (int i = 0, j = 0; i < strlen(aimS); i++) {
while (j != 0 && aimS[i] != moduleS[j]) j = next[j];
if (aimS[i] == moduleS[j]) j++;
if (j == strlen(moduleS)) {
int begin = i - strlen(moduleS) + 1;
int end = i;
printf("%d %d\n", begin, end);
j = next[j - 1] + 1;
}
}
}
int main() {
char aimS[N], moduleS[N];
int next[N];
scanf("%s", aimS);
scanf("%s", moduleS);
getNext(next, moduleS);
for (int i = 0; i < strlen(moduleS); i++) printf("%d ", next[i]);
puts("");
KMP(next, aimS, moduleS);
return 0;
}
|
第四章 上手真题
第五章 比赛怎么用
