题目链接
题目
我们规定对一个字符串的shift操作如下：
shift(“ABCD”, 0) = “ABCD”
shift(“ABCD”, 1) = “BCDA”
shift(“ABCD”, 2) = “CDAB”
换言之, 我们把最左侧的N个字符剪切下来, 按序附加到了右侧。
给定一个长度为n的字符串，我们规定最多可以进行n次向左的循环shift操作。如果shift(string, x) = string (0＜= x ＜n), 我们称其为一次匹配(match)。求在shift过程中出现匹配的次数。
输入
输入仅包括一个给定的字符串，只包含大小写字符。样例输入byebyebye
输出
输出仅包括一行，即所求的匹配次数。样例输出3
时间限制
C/C++语言：1000MS其它语言：3000MS
内存限制
C/C++语言：65536KB其它语言：589824KB
完整代码
暴力
运行结果：超时
ac40%
#include<bits/stdc++.h>using namespace std;string shift(string str, int n){string res = ""; res = str.substr(n, str.length() - n) + str.substr(0, n); return res;}int main(){string str = ""; cin >> str; int res = 0; for(int i = 0; i < str.length(); ++i){if(str == shift(str, i)) ++res; } cout << res;return 0; }
暴力优化
如果数组中每个字符都相同，则直接输出长度移动时，移动的长度是总长度的因数时才移动结果：ac:60%,总是显示测试用例：zzzz时出错，但程序在输入：zzzzz,结果就是5啊！！！
#include<bits/stdc++.h>using namespace std;string shift(string str, int n){string res = ""; res = str.substr(n, str.length() - n) + str.substr(0, n); return res;}int main(){string str = ""; cin >> str; int j = 1;while(j < str.length()){if(str[j] == str[j - 1])++j;elsebreak;}if(j == str.length()){cout << j;return 0;}int res = 0; for(int i = 0; i < str.length(); ++i){if(str.length() % (i + 1))continue;if(str == shift(str, i)) ++res; } cout << res;return 0; }
借助KMP算法
KMP
相当于求字符串的周期，最终长度除以周期就是结果利用s.length() - next[s.length()]就是周期
ac了
#include<bits/stdc++.h>using namespace std;int GetNext(string s){vector<int> next(s.length() + 1);//注意和KMP的区别next[0] = -1;int k = -1, j = 0;while(j < s.length()){if(k == -1 || s[k] == s[j]){//KMP的next数组未优化形式++k;++j;next[j] = k;}else{k = next[k];}}return next[s.length()];}int main(){string s;cin >> s;if(s.length() == 0){cout << 0;return 0;}int t = s.length() - ((GetNext(s)));if(s.length() % t == 0)cout << s.length() / t ;elsecout << 1;return 0;}
