图解扩展 kmp

#include <bits/stdc++.h>
#define MX 100005

using namespace std;

char s[MX], t[MX];      //To calculate lcp of every prefix of s and string t
int nt[MX], ans[MX];    //t's next array, and answer array
int ls, lt;             //length of s and t

void prework(char *str, int *lcp, int n)
{
    int k = 0, p = 1;
    lcp[0] = n;
    for(int i=1; i<n; i++)
    {
        lcp[i] = max(min(lcp[i-k], p-i), 0);
        while(str[i+lcp[i]] == str[lcp[i]]) lcp[i]++;
        if(i+lcp[i] > p) p = i+lcp[i], k = i;
    }
}

void work(char *a, char *b, int *lcp, int *des, int n, int m)
{
    int k = 0, p = 1;
    for(int i=0; i<n; i++)
    {
        des[i] = max(min(lcp[i-k], p-i), 0);
        while(a[i+des[i]] == b[des[i]]) des[i]++;
        if(i+des[i] > p) p = i+des[i], k = i;
    }
}

int main()
{
    scanf("%s", s);
    scanf("%s", t);
    ls = strlen(s);
    lt = strlen(t);
    prework(t, nt, lt);
    work(s, t, nt, ans, ls, lt);
    for(int i=0; i<lt; i++) printf("%d ", nt[i]); putchar('\n');
    for(int i=0; i<ls; i++) printf("%d ", ans[i]); putchar('\n');
    return 0;
}