Period II---fzu1901（Next数组）

题目链接：http://acm.fzu.edu.cn/problem.php?pid=1901

给你一个字符串 s 求出所有满足s[i] == s[i+p] ( 0 < i+p < len )的 p ;

kmp中Next[i] 表示前i个字符的前缀和后缀的最大匹配 s[0--x] == s[i-x-1 --- i] ;

下面是看别人的解释：

•知识点：KMP算法、对next数组的理解

•KMP算法中next数组的含义是什么？

•next数组：失配指针

•如果目标串的当前字符i在匹配到模式串的第j个字符时失配，那么我们可以让i试着去匹配next(j)

•对于模式串str，next数组的意义就是：

•如果next(j)=t,那么str[1…t]=str[len-t+1…len]

•我们考虑next(len)，令t=next(len);

•next(len)有什么含义？

•str[1…t]=str[len-t+1…len]

•那么，长度为len-next(len)的前缀显然是符合题意的。

•接下来我们应该去考虑谁？

•t=next( next(len) );

•t=next( next (next(len) ) );

• 一直下去直到t=0,每个符合题意的前缀长是len-t

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<stdlib.h>

using namespace std;

const int N = 1e6+;

char s[N];

int Next[N], ans[N];

void GetNext(char a[], int n)

{

    int i=, j=-;

    Next[] = -;

    while(i<n)

    {

        if(j==- || a[i]==a[j])

            Next[++i] = ++j;

        else

            j = Next[j];

    }

}

int main()

{

    int T, t=, k, len;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%s", s);

        len = strlen(s);

        GetNext(s, len);

        k = ;

        for(int j=len; j>; j=Next[j])

            ans[k++] = len - Next[j];

        printf("Case #%d: %d\n", t++, k);

        for(int i=; i<k; i++)

            printf("%d%c", ans[i], i==k-?'\n':' ');

    }

    return ;

}

巴特西

Period II---fzu1901（Next数组）

最新文章

热门文章