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

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");
    }
}