当前位置: 代码迷 >> 综合 >> Periodic Srings, UVa445
  详细解决方案

Periodic Srings, UVa445

热度:93   发布时间:2023-10-20 19:33:24.0

题目就不重述了,相信能找到这的人都知道题目是啥了。

大致就是字符串的最小周期,比如“abcabc”的最小周期为3。

#include<stdio.h>
#define maxn 80+10
#include<string.h>int main()
{char s[maxn];scanf("%s",s);int len = strlen(s);int i,j;int period = 0;for(i=1;i<len;i++){int k=0;int l=i;for(j=i;j<len;){if(s[k]!=s[l]){if(l==len-1){period = len;break;}break;}k++;l++;if(l==len && k==j){period = i;break;}}if (period!=0)break;}printf("%d",period);
}

思路是:

假设周期为1,比较第1位和第2位是否相同,如果不同,自然说明周期是要大于1的。

周期++,继续这时候判断第1位和第3位是否相同,如果不同,周期++;

如果相同,判断第2位和第4位是否相同,以此类推。

难点应该在于终止条件的设置。我用k和l跟踪将要对比是否相同的字符的index,如果s[k]不等于s[l]且l追踪到最后一个位置了,说明周期等于字符长度。如果是s[k]等于s[l]且l已经等于字符长度且k等于最开始对比的j的位置,则说明周期就是当前的i。