POJ2406简单KMP

题意：

给一个字符串，求最大的前缀循环周期，就是最小的循环节对应的最大的那个周期。

思路：

KMP的简单应用，求完next数组后有这样的应用：next[i] ：是最大循环节的第几位，比如123451234512那么就是7循环节是1234512345

i-next[i] :最小循环节的位数if（next[i] && i % (next[i])==0）那么 i / (i - next[i]) 就是最大的周期数（这个题目用的就是这个）

<strong><span style="font-size:18px;">#include<stdio.h>

#include<string.h>

char str[1000005];

int next[1000005];

void Get_Next(int m)

{

    int j = 0 ,k = -1;

    next[0] = -1;

    while(j<m)

    {

        if(k == -1 || str[j] == str[k])

        next[++j] = ++k;

        else k = next[k];

    }

    return ;

}

int main ()

{

    int i ,n;

    while(~scanf("%s" ,str) && str[0] != '.')

    {

        n = strlen(str);

        Get_Next(n);

        if(next[n] && n % (n - next[n]) == 0)

        printf("%d\n" ,n / (n - next[n]));

        else printf("1\n");

    }

    return 0;

}

</span></strong>

巴特西

POJ2406简单KMP

最新文章

热门文章