题目描述
给定两个字符串 a 和 b,我们定义 a×b 为他们的连接。
例如,如果 a=abc 而 b=def, 则 a×b=abcdef。
如果我们将连接考虑成乘法,一个非负整数的乘方将用一种通常的方式定义:
$a = $‘ ’(空字符串),a^(n+1)=$a×(a^n)$。
输入格式
输入包含多组测试样例,每组测试样例占一行。
每组样例包含一个字符串 S,S 的长度不超过 100。
最后的测试样例后面将是一个点号作为一行。
输出格式
对于每一个 S,你需要输出最大的 n,使得存在一个字符串 a,让 $S = a^n$。
样例
输入样例:
abcd
aaaa
ababab
.
输出样例:
1
4
3
算法1
循环查找最小循环子串
C++ 代码
#include <iostream>
using namespace std;
int main()
{
string str;
while (cin >> str, str != ".")
{
int k = 1;
while (k <= str.size())
{
if (str.size() % k == 0)
{
bool flag = true;
for (int i = k; i < str.size(); i += k)
for (int j = 0; j < k; j ++ )
if (str[j] != str[i + j])
flag = false;
if (flag) break;
}
k ++ ;
}
cout << str.size() / k << endl;
}
return 0;
}
算法2
找规律快速确定最小循环子串
规律——先将数据的循环子串分为两类:一类为子串内部有重复字符,一类为子串内部无重复字符。
由 $S = a^n$ 可知:
1、如果子串内部无重复字符,那么循环子串的最大个数就是其中任意一个字符出现的个数,因为所有字符出现次数相同。
2、如果子串内部有重复字符,那么循环子串的最大个数就是其中不重复字符出现的个数,即找到出现次数最少的那个字符的个数即可。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
string s;
while(cin >> s,s != ".")
{
int b[130] = {0}, max = 0 ,min = 100;
for (int i = 0; i < s.size(); i ++ )
{
b[s[i]] ++;
if(b[s[i]] > max)
max = b[s[i]];
}
for (int i = 0; i < s.size(); i ++ )
{
if(b[s[i]] < min && b[s[i]] < max)
min = b[s[i]];
}
if(max > min)
cout << min << endl;
else
cout << max << endl;
}
return 0;
}
你好,请问当输入为”aabb”时,该怎么办呢?应该是(aabb)^1,答案为1才对,按照你的写法,答案是2。
题目问的是最大的s哦
膜拜大佬啊