HDU 2434 Period

继续切水题的我。

这道题算法KMP

然后你只需要在做KMP的时候看一下i%(i-next[i])是否等于0且next[i]不为0

如果是0说明这里有循环节(不信你可以自己模拟一下QAQ)

Code:

#include<cstdio>
#include<algorithm>
using namespace std;
char st[1100000];
int s[1100000];
int n,cnt;
int main()
{
    scanf("%d",&n);
    while (n)
    {
        cnt++;
        printf("Test case #%d\n",cnt);
        scanf("%s",st+1);
        for (int i=2;i<=n;i++)
        {
            int t=s[i-1];
            while (t>0&&st[t+1]!=st[i]) t=s[t];
            if (st[t+1]==st[i]) t++;
            s[i]=t;
            if (i%(i-s[i])==0&&s[i]!=0) printf("%d %d\n",i,i/(i-s[i]));
         } 
         printf("\n");
        scanf("%d",&n);
    }
}

1 thought on “HDU 2434 Period”

  1. I just wanted to write a quick word in order to say thanks to you for some of the great ways you are giving out on this site. My incredibly long internet research has at the end of the day been honored with incredibly good details to talk about with my family members. I would declare that we site visitors are quite fortunate to be in a remarkable community with very many marvellous professionals with great guidelines. I feel quite grateful to have come across the web page and look forward to so many more entertaining times reading here. Thanks a lot once again for a lot of things.

Leave a Comment

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