【模板】KMP

北路人

于 2018-08-08 08:41:00 发布

阅读量158

点赞数 3

本文链接：https://blog.csdn.net/jokingcoder/article/details/81459084

版权

#include <cstdio>
#include <cstring>
#define N 1000010

using namespace std;
char s[N],t[N];
int next[N];

int main() {
    scanf("%s%s", s, t);
    int m = strlen(s), n = strlen(t);
    next[0] = -1;
    for (int i = 1; i < n; i++) {
        int k = next[i - 1];
        while (k > -1 && t[k + 1] != t[i])
            k = next[k];
        if (t[k + 1] == t[i]) k++;
        next[i] = k;
    }
    int k = 0;
    for (int i = 0; i < m; i++) {
        while (k > -1 && s[i] != t[k + 1])
            k = next[k];
        if (s[i] == t[k + 1]) k++;
        if (k == n - 1) {
            k = next[k];
            printf("%d\n", i - n + 2);
        }
    }
    for (int i = 0; i < n; i++)
        printf("%d ", next[i] + 1);
    return 0;
}