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
思路: 这个题有意思, 让我发现了 string 里面的 substr 函数, 但是更有意思的是, 字符串的长度有点儿那么太大啊!
- #include<cstdio>
- #include<queue>
- #include<vector>
- #include<string>
- #include<iostream>
- #include<functional>
- #include<algorithm>
- using namespace std;
- char a[1000005];
- int main()
- {
- string str;
- cin>> str;
- if (str.length() % 2 != 0){
- cout << "NO" << endl;
- return 0;
- }
- int len = str.length() / 2;
- string cstr = str.substr(1) + str[0];
- if (cstr == str){
- cout << "YES" << endl;
- return 0;
- }
- while (cstr != str){
- //cout << cstr.substr(0, len) << " " << cstr.substr(len) << endl;
- if (cstr.substr(0, len) == cstr.substr(len)){
- cout << "YES" << endl;
- return 0;
- }
- else cstr = cstr.substr(1) + cstr[0];
- }
- cout << "NO" << endl;
- return 0;
- }
- substr-TLE
后续: 这个题真的是很有意思真的是很有意思有意思, 请手动写对串旋转之后的两三个, 你将发现新大陆. AC 代码都不想贴
来源: http://www.bubuko.com/infodetail-2633764.html