欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《算法竞赛入门经典》(第2版) 习题3-4 周期串

程序员文章站 2022-06-02 22:14:46
...

题目

习题3-4 周期串(Periodic Strings, UVa455)
如果一个字符串可以由某个长度为k的字符串重复多次得到,则称该串以k为周期。 例如,abcabcabcabc以3为周期(注意,它也以6和12为周期)。输入一个长度不超过80的字符串,输出其最小周期。

Uva的OJ上的英文原题
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 oif 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

解题思路

求最小周期串,那就从长度1开始遍历,找到一个满足条件的最小字符子串即可。

我提交了五六次最终才AC,一直觉得自己的思路没问题,但是前几次就是WA、WA。。。最后AC是因为加入了一个判断条件,当子串长度不能被总长度整除时,不进行判断,继续遍历。(我一开始加入这一行,单纯只是学习别人的思路,这行加入可以提高程序效率)

然后我就蛮提交了一下,竟然PE了,那说明答案对了!只是输出格式有点问题,然后改了一下Output空行的问题,AC了!!!我瞬间惊醒,我去!!!我的judge函数有漏洞!!!

如果不判断周期串能否被总长度整除,会出现如下情况,即Wrong Answer:
《算法竞赛入门经典》(第2版) 习题3-4 周期串
具体原因是:我的判断函数是用子串与后面的字符进行比较,若出现不等的情况,则子串不是周期串,返回0。若没出现不等的情况,则为周期串,返回真值1。以上例子输入:AABBAAB,最终用AABB进行判断,后面的字符串AAB并没有找到不等的,就返回1,输出答案4了,但是是错的呀。

解决方法就是我误打误撞的加入判断条件,周期串长度必须要能被总长度整除。

AC代码(在Uva的OJ)

在后面AC不了的时候,看了一些别人的代码,还是觉得自己的代码更简单明了、优美。(嘻嘻,撇开那个大BUG不说)

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

int judge(string ss, int per) {
	for (int i = per; i < ss.length(); i++) {
		if (ss[i % per] != ss[i]) return 0;	//若找到不等的,则不是周期串 
	}	
	return 1;
}

int main() {
	int n;
//	freopen("data.out.txt", "w", stdout);
	cin >> n;
	int count = 0;
	while(n--) {
		string ss;
		cin >> ss;
		int len = ss.length();
		int per = 1;
		for (int i = 0; i < len; i++) {
			if (len % (i+1) != 0) continue;	//周期肯定能被长度整除的 !!!
			if (judge( ss, i+1)) {
				per = i+1;
				break;
			}
		}
		count ++;	//打空行用的 
		if (count > 1) cout << endl;
		cout << per << endl;
	}
	
	return 0;
}