Periodic Strings UVA - 455
A character string is said to have period k if it can be formed by concatenating one or more repetitions of another string of length k. For example, the string ”abcabcabcabc” has period 3, since it is formed by 4 repetitions of the string ”abc”. It also has periods 6 (two repetitions of ”abcabc”) and 12 (one repetition of ”abcabcabcabc”).
Write a program to read a character string and determine its smallest period.
Input
The first line of the input file will contain a single integer N indicating how many test case that your program will test followed by a blank line. Each test case will contain a single character string of up to 80 non-blank characters. Two consecutive input will separated by a blank line.
Output
An integer denoting the smallest period of the input string for each input. Two consecutive output are separated by a blank line.
Sample Input
1
HoHoHo
Sample Output
2
HINT
这个题目是要求求一个字符串的周期如:521521521的周期就是521的长度3。
解题思路就是将整个字符串进行切片处理,分成若干个可能的子字符串逐个判别,这样要解决的问题就有:
1.切除来的若干个等长字串如何保证等长?
利用相除取余来判断余数是否为零来解决。
2.切出来的等长字串如何来判断其是相等的?
将第一个字串作为标准,将其它子串的对应位置的字符进行比较来判断是否满足要求。注意看后面代码如何计算其他字串对应位 置的。
注意:输出的格式要求最后一个数字只有一个回车而其他的都有两个回车!!!
Accepted
#include<stdio.h>
#include<string.h>
int main()
{
int sum;
scanf("%d", &sum);
while(sum--)
{
char s[85];
scanf("%s", s);
int len = strlen(s);
int flag = 0;
for (int i = 1;i <= len;i++) //第一个循环来尝试找出可能的周期
{
if (len % i != 0)continue;
for (int j = 0;j < i;j++) //第二、第三个循环来按照选定的周期对字符串进行切片判断。
{
flag = 0;
for (int k = 1;k <= len / i;k++) //len/i切出来的子串的个数
{
if (k*i+j<len&&s[j] != s[k * i+j]) //每一次比较一个子串的对应位置的字符是否和第一个字串对应位置处的字符相等。
{
flag = 1;
break;
}
}
if (flag)break;
}
if (!flag&&sum!=0)
{
printf("%d\n\n", i);
break;
}
else if (!flag && sum == 0)
{
printf("%d\n", i);
break;
}
}
if (flag && sum != 0) //注意区分最后一个数字的输出格式
printf("%d\n\n", len);
else if (flag && sum == 0)
printf("%d\n", len);
}
}
最新文章
- 51nod1174(RMQ)
- VA01复制单据,更新定价日期和价格
- poj3693
- AutoHotkey之自问自答
- 转帖一篇sixxpack破解的文章!
- 捋一捋Javascript数据类型转换规则
- ASP.NET MVC 模型和数据对象映射实践
- 关于sql语句in的使用注意规则
- webstorm 如何配置git
- 头像上传ASP.NET MVC实现-可拖动大小实时预览
- 怎么给iOS项目打包
- 关于在transform下的子元素设置fixed无效的困惑
- extern用法汇总
- 从零安装Scrapy心得 | Install Python Scrapy from scratch
- configure文件的生成
- Spring在web开发中的应用
- 2.docker的网络模式
- 709. To Lower Case
- 面试知识点——Java
- Redis进阶之redis的生命周期