注意事项：无。

Luogu P3375 【模板】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
int fail[MAXlenb + 10];
void evafail(int lenb, char *b) {
    int j = 0;
    fail[1] = j;
    for (int i = 2; i <= lenb; ++i) {
        while (j && b[j + 1] != b[i]) j = fail[j];
        if (b[j + 1] == b[i]) ++j;
        fail[i] = j;
    }
}
bool ismatch[MAXlena + 10];
void match(int lena, char *a, int lenb, char *b) {
    int j = 0;
    for (int i = 1; i <= lena; ++i) {
        while (j && (j == lenb || b[j + 1] != a[i])) j = fail[j];
        if (b[j + 1] == a[i]) ++j;
        if (j == lenb) ismatch[i - lenb + 1] = 1;
    }
}

int lena; char a[MAXlena + 10];
int lenb; char b[MAXlenb + 10];
signed main() {
    scanf("%s", a + 1);
    lena = strlen(a + 1);
    scanf("%s", b + 1);
    lenb = strlen(b + 1);
    evafail(lenb, b);
    match(lena, a, lenb, b);
    for (int i = 1; i <= lena; ++i) {
        if (ismatch[i]) {
            printf("%d\n", i);
        }
    }
    for (int i = 1; i <= lenb; ++i) {
        printf("%d ", fail[i]);
    }
    puts("");
    return 0;
}