# 图解扩展 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;
}


### 3 条评论

Orz，abs 大佬の算法课堂！

Orz 强记学算法中。。。

#### XZYQvQ · 2018年6月20日 10:00 下午

一年后，我终于看懂了扩展 kmp