链接:

https://www.luogu.org/problem/P5410#submit

题意:

有两个字符串aa,bb,要求输出bb与aa的每一个后缀的最长公共前缀

思路:

扩展kmp模板, 上一个大佬的详解链接

https://segmentfault.com/a/1190000008663857

代码:

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+10;

char a[MAXN], b[MAXN];

int Next[MAXN], Exten[MAXN];

void GetNext(char *t)

{

    int p = 0, a = 0;

    int len = strlen(t);

    Next[0] = len;

    for (int i = 1;i < len;i++)

    {

        if (i >= p || i+Next[i-a] >= p)

        {

            if (i >= p)

                p = i;

            while (p < len && t[p] == t[p-i])

                p++;

            Next[i] = p-i;

            a = i;

        }

        else

            Next[i] = Next[i-a];

    }

}

void ExKmp(char *s, char *t)

{

    int a = 0, p = 0;

    int len = strlen(s);

    GetNext(t);

    for (int i = 0;i < len;i++)

    {

        if (i >= p || i+Next[i-a] >= p)

        {

            if (i >= p)

                p = i;

            while (p < len && s[p] == t[p-i])

                p++;

            Exten[i] = p-i;

            a = i;

        }

        else

            Exten[i] = Next[i-a];

    }

}

int main()

{

    scanf("%s %s", a, b);

    ExKmp(a, b);

    for (int i = 0;i < strlen(b);i++)

        printf("%d ", Next[i]);

    puts("");

    for (int i = 0;i < strlen(a);i++)

        printf("%d ", Exten[i]);

    puts("");

    return 0;

}

巴特西

洛谷-p5410-扩展KMP模板

链接:

题意:

思路:

代码:

最新文章

热门文章