今天我刷题了吗
搜索文档…
KMP 算法
1
void getNext(char* p)
2
{
3
int len = (int)strlen(p + 1);
4
for (int i = 2, j = 0; i <= len; i++) {
5
while (j && p[i] != p[j + 1]) j = nxt[j];
6
if (p[i] == p[j + 1]) j++;
7
nxt[i] = j;
8
}
9
}
10
11
void kmp(char* s, char* p)
12
{
13
int slen = (int)strlen(s + 1), plen = (int)strlen(p + 1);
14
for (int i = 1, j = 0; i <= slen; i++) {
15
while (j && s[i] != p[j + 1]) j = nxt[j];
16
if (s[i] == p[j + 1]) j++;
17
if (j == plen) {
18
printf("%d\n", i - plen + 1);
19
j = nxt[j];
20
}
21
}
22
}
Copied!
最近更新 1yr ago
复制链接