DLKKILL

DLKKILL's world

POJ - 1961 - Period (KMP的next数组运用)

题目链接: POJ – 1961

题目大意:

求前缀子串中,可以循环表示的子串

题目分析:

KMP,利用KMP的next的性质,观察一下即可

给出代码:

#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
const int maxn=1000000+10;
int len;
string s;
int nexts[maxn];
void init()
{
    memset(nexts,0,sizeof(nexts));
}
void get_next()
{
    int n=len;
    int i=0;
    int j=-1;
    nexts[0]=-1;
    while(i<n)
    {
        if(j==-1||s[i]==s[j])
        {
            i++;
            j++;
            nexts[i]=j;
        }
        else
            j=nexts[j];
    }
    return;
}
int main()
{
    int kase=0;
    while(cin>>len&&len)
    {
        cin>>s;
        init();
        get_next();
       /* for(int i=0; i<=len; i++)
        {
            cout<<" "<<nexts[i];
        }
        cout<<endl;*/
        printf("Test case #%d\n",++kase);
        for(int i=1; i<=len; i++)
        {
                int t=i-nexts[i];
               // cout<<t<<" "<<i<<endl;
                if(t!=0&&i%t==0&&i/t>1)
                    cout<<i<<" "<<i/t<<endl;
        }
        cout<<endl;
    }
    return 0;
}

点赞

发表评论

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