hdu1358 Period

　　首先给个博客：http://blog.csdn.net/lttree/article/details/20732385

　　感觉他说的很好，尤其是引用的那个博客，清晰的说明了循环节的两个公式。

　　http://www.cnblogs.com/jackge/archive/2013/01/05/2846006.html

　　那我就在重复一遍，这两个公式这的很重要。

对于这个循环节就是两个公式，

在i位置可以判断0~i-1的循环：

如果i%(i-next[i])==0 那么就有循环，并且next[i]!=0,

循环次数为 i/(i-next[i])

循环长度为 i-next[i]

这题还有一个坑的地方，我在代码里注释了，就是先要赋值dd，在循环，否则真的会超时，，，，坑死我了 = =

for (int i=2;i<=strlen(str);i++) 就是说这样是错的

#include <bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;
typedef long long LL;
#define PI(A) printf("%d
",A)
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d%d",&(N),&(M))
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,b) for(int i=0;i<(b);i++)
#define Rep(i,a,b) for(int i=(a);i<=(b);i++)
#define reRep(i,a,b) for(int i=(a);i>=(b);i--)
//#define next Next
const double EPS= 1e-9 ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN= 1000000 + 5 ;

//kuangbin 模板
//Next[]调用的时候不需要初始化
int Next[MAXN];
void kmp_pre(char x[])
{
    int m=strlen(x);
    int i,j;
    j=Next[0]=-1;
    i=0;
    while(i<m)
    {
        while(-1!=j&&x[i]!=x[j]) j=Next[j];
        Next[++i]=++j;
    }
}


char str[MAXN];
int N,k;

int main()
{
    while(~SI(N),N)
    {
        scanf("%s",str);
        kmp_pre(str);
        
        //特别注意这里，一定要先把strlen(str)的值赋给dd  不能直接for (int i=2; i<=strlen(str); i++) 这样会TLE
        int dd=strlen(str);
        
        printf("Test case #%d
",++k);
        //注意注意 
        for (int i=2; i<=dd; i++)
        {
            int d=i-Next[i];
            if (i%d==0&&i>d)
            {
                printf("%d %d
",i,i/d);
            }
        }
        puts("");
    }
    return 0;
}

 第二遍，自己写的AC代码

#include <bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;
typedef long long ll;
#define PU puts("");
#define PI(A) printf("%d
",A)
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d%d",&(N),&(M))
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,b) for(int i=0;i<(b);i++)
#define Rep(i,a,b) for(int i=(a);i<=(b);i++)
#define reRep(i,a,b) for(int i=(a);i>=(b);i--)
const double EPS= 1e-9 ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN= 1000000+9 ;
int Next[MAXN];
int len;
char x[MAXN];

void kmp_pre()
{
    int i,j;
    j=Next[0]=-1;
    i=0;
    while(i<len)
    {
        while(-1!=j&&x[i]!=x[j])j=Next[j];
        Next[++i]=++j;
    }
}
int T;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("C:\Users\Zmy\Desktop\in.txt","r",stdin);
//    freopen("C:\Users\Zmy\Desktop\out.txt","w",stdout);
#endif
    while(~SI(len),len)
    {
        scanf("%s",x);
        kmp_pre();
        printf("Test case #%d
",++T);
        for (int i=2; i<=len; i++)
        {
            if (i%(i-Next[i])==0&&Next[i]!=0)
            {
                //i-Next[i]是循环串的长度，总长   除   循环串的长度就是 次数
                //                        i     /    (i-Next[i])
                printf("%d %d
",i,i/(i-Next[i]));
            }
        }
        PU;
    }
    return 0;
}