当前位置: 代码迷 >> 综合 >> 【UVA1328】Period
  详细解决方案

【UVA1328】Period

热度:21   发布时间:2023-12-05 12:36:33.0

题意

??给定一个字符串S,求该字符串每一个前缀的循环节长度,如果循环节长度不为1则输出(格式看题目)

解法

KMP
??首先想这么一个问题:给定一个字符串S,由 n 个子串重复得到,求最大的n
如果给定一个前缀 Sk ,存在m,使得 Skm=S ,显然有:|S| % k=0,而且S的前 k 个字符必定等于S的后 k 个字符。实际上这一个性质是m存在的充要条件
如果 S 的前k个字符等于 S 的后k个字符,那么可以把 S 分为|S|k段,根据条件可以得到:第一段等于第二段,第二段等于第三段……因此存在一个m
那要如何判断 S 的前k个字符是否等于 S 的后k个字符?可以使用 Next 数组:Nexti表示的对于前缀S1S2Si中最长的一个前缀的长度,满足等长的后缀与其相等(不包括自身),因此我们只需要求出S Next 数组,然后对于一个前缀Si(字符串从1开始),如果存在m使得有 Cm=Si ,那么就必须满足i% i?Nexti=0 m=ii?Nexti

复杂度

O(T?n

代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
#define Rint register int
#define Lint long long int
using namespace std;
const int L=1000010;
char s[L];
int Next[L],n;
void getNext()
{Next[0]=0;int i=1,j=0;while( i<=n-1 ){while( j && s[j]!=s[i] )   j=Next[j-1];if( s[j]==s[i] )   j=j+1;Next[i]=j;i=i+1;}
}
int main()
{int C=0;while( scanf("%d",&n)!=EOF ){if( !n )   break ;printf("Test case #%d\n",++C);for(int i=0;i<=n;i++)   Next[i]=0;scanf("%s",s);getNext();for(int i=0,x;i<=n-1;i++){x=(i+1)/(i+1-Next[i]);if( x!=1 && x*(i+1-Next[i])==i+1 )   printf("%d %d\n",i+1,x);}printf("\n");}return 0;
}