【51NOD刷题】1347 旋转字符串

1347 旋转字符串

基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题

S[0…n-1]是一个长度为n的字符串,定义旋转函数Left(S)=S[1…n-1]+S[0].比如S=”abcd”,Left(S)=”bcda”.一个串是对串当且仅当这个串长度为偶数,前半段和后半段一样。比如”abcabc”是对串,”aabbcc”则不是。
现在问题是给定一个字符串,判断他是否可以由一个对串旋转任意次得到。

输入输出

Input
第1行:给出一个字符串(字符串非空串,只包含小写字母,长度不超过1000000)
Output
对于每个测试用例,输出结果占一行,如果能,输出YES,否则输出NO。
Input示例

aa
ab

Output示例

YES
NO

C#的运行时限为:1500 ms ,空间限制为:196608 KB

题目解析

从旋转函数定义来看,将字符串第一个字符移动到字符串的末尾,很容易想当然的以为需要进行Length-1次循环判断完所有旋转后的结果。
题目中输入字符串长度最多为1,000,000,最多需要500,000次判断才能得出该字符串是否为对串,如果进行Length-1次循环,那计算次数最多会达到500,000,000,000,结果必然是超时。

而实际上,当一个字符串是对串(即前半段和后半段完全相同的字符串)时,它无论经过多少次旋转都依然还是对串,所以只需要对输入字符串进行一次判断即可。

Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using System;

public class Sum
{
public static void Main()
{
var str = Console.ReadLine();
if (str.Length % 2 != 0)
{
Console.WriteLine("NO");
return;
}
var strQueue = str.ToCharArray();
for (var j = 0; j < strQueue.Length / 2; j++)
{
if (strQueue[j] == strQueue[strQueue.Length / 2 + j]) continue;
Console.WriteLine("NO"); ;
return;
}
Console.WriteLine("YES");
}
}

欢迎关注我的其它发布渠道