[模拟赛FJOI Easy Round #2][T1 sign] (模拟+求字符串重复字串)

【题目描述】

小Z在无意中发现了一个神奇的OJ，这个OJ有一个神奇的功能：每日签到，并且会通过某种玄学的算法计算出今日的运势。在多次试验之后，小Z发现自己的运势按照一定的周期循环，现在他找到了你，请通过他的记录，找出他运势的循环节。

【输入数据】

第一行一个整数n，表示小Z记录的天数

接下来n行，表示每天的运势，用一个正整数表示，相同的整数表示相同的运势，不同的整数表示不同的运势。

【输出数据】

一行若干个整数表示所有可能的小于等于n的循环节。

【样例输入】

1 2 1 1 2 1

【样例输出】

3 5 6

【数据范围】

对于100%的数据，n<=365，每天的运势不会爆int

Solution

果然是签到题。

当然最暴力的解法是O(n*n*n)

这里数据范围比较小，我们考虑O(n*n)的算法

先枚举重复串的长度，判断时，用错位比较法

如果当前枚举的长度为k，匹配后缀S(1)和后缀S(k+1)的最长公共前缀是n-k的话，证明k是一个符合本题题意的循环节

要优化的话不能用后缀数组，用个kmp吧，我倒是直接暴力了

#include<stdio.h>

#include<string.h>

#define N 400

inline int Rin(){

  int x=,c=getchar(),f=;

  for(;c<||c>;c=getchar())

    if(!(c^))f=-;

  for(;c>&&c<;c=getchar())

    x=(x<<)+(x<<)+c-;

  return x*f;

}

int n,a[N],top,pb[N];

inline bool jud(int k){

  for(int i=;i<=n-k;i++)

    if(a[i]^a[k+i])

      return false;

  return true;

}

int main(){

  freopen("sign.in","r",stdin);

  freopen("sign.out","w",stdout);

  n=Rin();

  for(int i=;i<=n;i++)

    a[i]=Rin();

  for(int i=;i<n;i++)

    if(jud(i))

      pb[++top]=i;

  for(int i=;i<=top;i++)

    printf("%d ",pb[i]);

  printf("%d\n",n);

  fclose(stdin);

  fclose(stdout);

  return ;

}

秒客网