关于周期性的问题

暂时遇到的是数字周期和字符串周期问题

题目 老虎机

给你一个n (n<1e$6$) ,再给你一个长度为n的序列(从0开始),保证从某一个位置k开始它具有周期性,
循环节长度为p,求k和p,且k+p要最小

样例

6
612534 3157 423 3157 423 3157

输出:
1 2

9
1 2 1 3 1 2 1 3 1

输出:
0 4

分析

题目第一眼看过去就感觉和kmp字符串求周期有点类似!!!
首先从某一个位置k开始它具有周期性!我们如果正着序列一个一个循环
不好找周期性,可以考虑倒着做,因为倒着从一开始就一定具有周期性!!
于是就是倒置后,求每个序列的最小正周期p,再变换出原来的位置k,k+p得比较一下
这里的ne数组和kmp的思想是一样的,只是存的是数字而不是字符

考试的时候没想到是用存数字(也不知道在想什么)
for(int i=2,j=0;i<=n;i++)
{
    while(j&&a[i]!=a[j+1])  j=ne[j];//有前缀匹配且当前不匹配
    if(a[i]==a[j+1])    j++;//匹配
    ne[i]=j;//更新ne
}

k,p的更新过程
序列存的时候是倒过来存的!!!

int k=1e9,p=1e9;
for(int i=1;i<=n;i++)
{
    int k1=n-i;//变换原来的编号,原来的编号是从0开始,n对应的就是0
    int p1=i-ne[i];//i-ne[i]反过来序列长度为i的时候它的循环节长度
    if(k1+p1<k+p)
    {
        k=k1,p=p1;//更新
    }
    else if(k1+p1==k+p&&p1<p)
    {
        k=k1,p=p1;
    }
}

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N];
int ne[N];
int n;
void kmp(){
    for(int i=2,j=0;i<=n;i++){
        while(j&&a[i]!=a[j+1]) j=ne[j];
        if(a[i]==a[j+1]) j++;
        ne[i]=j;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=n;i>=1;i--) scanf("%d",&a[i]);//先反着放
    int k=1e9,p=1e9;
    kmp();
//    for(int i=1;i<=n;i++) cout<<ne[i]<<endl;
    for(int i=1;i<=n;i++){
        int k1=n-i;//开始处
        int p1=i-ne[i];//循环节
        if(k1+p1<k+p){
            k=k1;
            p=p1;
        }
        else if(k1+p1==k+p&&p1<p){
            k=k1;
            p=p1;
        }
    }
    cout<<k<<" "<<p<<endl;
    return 0;
}

下面就是经典的字符串周期问题

题目 周期

安利一个博文 精彩的分析
给你一个字符串,输出所有的具有循环节的总长度和循环节出现次数(没有就不输出)

样例

12
aabaabaabaab

输出
2 2
6 2
9 3
12 4

主要的分析可以看上面的博文!!!
这里写一下算法流程

for(int i=2;str[i];i++)//枚举题目要求的具有循环节的字串结尾字符
{
    int t=i-ne[i];//循环节的长度
    if(t!=i&&i%t==0) printf("%d %d\n",i,i/t);//t==i是没意义的,这循环节只出现一次不满足题意
    //并且i%t==0,代表循环了多次
}

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int Next[N];
char str[N];
void get_next(){
    for(int i=2,j=0;str[i];i++){
        while(j&&str[i]!=str[j+1])  j=Next[j];
        if(str[i]==str[j+1])    j++;
        Next[i]=j;
    }
}
int main(){
    int n,m,T=1;
    while(cin>>n,n){
        cin>>str+1;
        get_next();
        printf("Test case #%d\n",T++);
        for(int i=2;str[i];i++){
            int t=i-Next[i];
            if(t!=i&&i%t==0){
                printf("%d %d\n",i,i/t);
            }

        }
       puts(""); 
    }
    return 0;
}