图解扩展 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 条评论

konnyakuxzy · 2017年6月15日 2:45 下午

Orz,abs 大佬の算法课堂!
太谢谢啦!

konnyakuxzy · 2017年6月12日 10:05 上午

Orz 强记学算法中。。。

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

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

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注