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 条评论
登录 后参与评论

相关文章

  • 优先队列(个人模版)

    优先队列: 1 struct node 2 { 3 int u,len; 4 friend bool operator <(...

    Angel_Kitty
  • LCT学习笔记

    最近自学了一下LCT(Link-Cut-Tree),参考了Saramanda及Yang_Zhe等众多大神的论文博客,对LCT有了一个初步的认识,LCT是一种动态...

    Angel_Kitty
  • 2017 Multi-University Training Contest - Team 9 1003&&HDU 6163 CSGO【计算几何】

    CSGO Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/65536 K (Ja...

    Angel_Kitty
  • 每天一道leetcode-392判断子序列

    给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000)...

    乔戈里
  • 每日算法题:Day 22(C/C++)

    牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它...

    算法工程师之路
  • #自媒体#新媒体课堂——自媒体平台知多少?自媒体平台有哪些?

    自媒体带起了一波创业者的高潮,做自媒体的主要就是两类人,要么是为了流量,获得用户关注;要么是为了阅读量,广告变现。说白了就是为了名利!

    夏末浅笑
  • IOS 使用Core Data读写数据库

    //项目创建成功后,在项目文件夹中将自动生成一个拥 有.xcdatamodelId扩展名的文件,该文件可以使用图形化的方式编辑数据 模型,在该文件中包含了E...

    用户5760343
  • php计算两个日期之间的间隔,避免导出大量数据

    在做系统业务功能的时候,有的时候业务人员会进行超大范围地导出excel表格,导致内存、CPU占用飙升。

    宣言言言
  • 关于编码解码问题,我给大家总结好了,请查收

    将一个十六进制字符串解码成一个字节字符串或者将一个字节字符串编码成 一个十六进制字符串。

    Python知识大全
  • 1号店CTO韩军:软件定义一切,人工智能是未来

    1号店的“智慧软件”能做哪些事情?它是如何炼成的?CSDN记者独家采访了1号店首席技术官兼技术部副总裁韩军,挖出了1号店在智慧软件、大数据和人工智能等领域的实践...

    CSDN技术头条

扫码关注云+社区

领取腾讯云代金券