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

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1347

分析:此题啊!超时啊。。。。一定要降低复杂度,之前写的复杂度为O(n^2),降低复杂度后,为O(n/2);

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     char s[1000005];
 6     while(gets(s))
 7     {
 8         int count=1;
 9         int len=strlen(s);
10         int t=len/2;
11         if(len%2!=0)
12             printf("NO\n");
13             else
14             {
15             for(int i=0;i<len/2;i++)
16             {
17                 if(s[i]!=s[i+t])
18                     {
19                         count=0;
20                         break;
21                     }
22             }
23             if(count)
24                 printf("YES\n");
25             else printf("NO\n");
26             }
27     }
28     return 0;
29 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏everhad

算法:排序

一些约定 java命令行程序 算法的学习和语言无关,下面使用一个java命令行程序来作为实例程序。 一个算法一个类 排序算法使用一个方法就可以表示,不需要是...

1886
来自专栏顶级程序员

说出来你们可能不信,但是数组名确实不是指针常量

这篇是一篇C语言劝退流教学文,看不懂的同学应该是劝退教学流的目标对象 (写完了才想起来注一下,本文提到的“数组”和“数组名”字样,指的是数组左值表达式(arr...

3706
来自专栏我是攻城师

JDK8中HashMap的工作原理剖析

49011
来自专栏企鹅号快讯

JAVA核心技术学习笔记

掌握Java核心技术是学习和掌握好Java技术的关键,下边分17个点对这些Java核心技术进行讲解。 >>>1.Java中没有多继承,而是用接口来代替多继承 >...

1895
来自专栏决胜机器学习

《Redis设计与实现》读书笔记(九) ——Redis集合和有序集合实现原理

《Redis设计与实现》读书笔记(九) ——Redis集合和有序集合实现原理 (原创内容,转载请注明来源,谢谢) 一、集合 集合的编码方式有intset和has...

3035
来自专栏沈唁志

PHP中系统函数http_build_query系统函数使用方法

1634
来自专栏赵俊的Java专栏

最大子数组

1345
来自专栏决胜机器学习

PHP数据结构(二十一) ——希尔排序

PHP数据结构(二十一)——希尔排序 (原创内容,转载请注明来源,谢谢) 一、概述 希尔排序,又称缩小增量排序,也属于插入排序类方法,时间上有较大改进。前面...

3407
来自专栏五分钟学算法

每天一算:Two Sum II

示例: 输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 i...

782
来自专栏决胜机器学习

PHP数据结构(二十六) ——基数排序实现36进制数排序

PHP数据结构(二十六)——基数排序实现36进制数排序 (原创内容,转载请注明来源,谢谢) 一、概述 插入排序、选择排序、快速排序等,都是通过关键字之间的比...

39911

扫码关注云+社区