poj 1961 Period

[cpp]
#include <iostream>  
#include <stdio.h>  
#include <string.h>  
using namespace std; 
const int maxn=1000001; 
char a[maxn]; 
int next[maxn],count[maxn]; 
int main() 
{ 
    int n; 
    int time=0; 
    while(scanf("%d",&n),n) 
    { 
        scanf("%s",&a[1]); 
        memset(next,0,sizeof(next)); 
    next[1]=0; 
    for(int i=2;i<=n;i++) 
    { 
        int tmp=next[i-1]; 
        if(a[tmp+1]==a[i]) 
        next[i]=tmp+1; 
        else 
        { 
            while(tmp!=0) 
            { 
                tmp=next[tmp]; 
                if(a[tmp+1]==a[i]) 
                { 
                    next[i]=tmp+1; 
                    break; 
                } 
            } 
        } 
    } 
    for(int i=1;i<=n;i++) 
    count[i]=1; 
 
    for(int i=1;i<=n;i++) 
    if(next[i]%(i-next[i])==0) 
    if(count[next[i]]==next[i]/(i-next[i])) 
    { 
        count[i]=count[next[i]]+1; 
    } 
 
    printf("Test case #%d\n",++time); 
 
    for(int i=1;i<=n;i++) 
    if(count[i]>=2) 
    printf("%d %d\n",i,count[i]); 
    printf("\n"); 
    } 
    return 0; 
} 

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn=1000001;
char a[maxn];
int next[maxn],count[maxn];
int main()
{
    int n;
    int time=0;
    while(scanf("%d",&n),n)
    {
        scanf("%s",&a[1]);
        memset(next,0,sizeof(next));
    next[1]=0;
    for(int i=2;i<=n;i++)
    {
        int tmp=next[i-1];
        if(a[tmp+1]==a[i])
        next[i]=tmp+1;
        else
        {
            while(tmp!=0)
            {
                tmp=next[tmp];
                if(a[tmp+1]==a[i])
                {
                    next[i]=tmp+1;
                    break;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    count[i]=1;

    for(int i=1;i<=n;i++)
    if(next[i]%(i-next[i])==0)
    if(count[next[i]]==next[i]/(i-next[i]))
    {
        count[i]=count[next[i]]+1;
    }

    printf("Test case #%d\n",++time);

    for(int i=1;i<=n;i++)
    if(count[i]>=2)
    printf("%d %d\n",i,count[i]);
    printf("\n");
    }
    return 0;
}

补充：软件开发 , C++ ,

上一个：数据结构试验 顺序表
下一个：数据结构实验 单链表