题目描述
给定两个字符串 a 和 b,我们定义 a×b 为他们的连接。
例如,如果 a=abc 而 b=def, 则 a×b=abcdef。
如果我们将连接考虑成乘法,一个非负整数的乘方将用一种通常的方式定义:$a^0$=``(空字符串),$a^{(n+1)}$=a×($a^n$)。
输入样例
abcd
aaaa
ababab
.
输出样例
1
4
3
算法流程
主要流程是确定当前最小字符串,并依次与剩余字符串取长度相同的字符串比较,若比较不相等,则改变最小字符串。
1、选择字符串s的起始位置为0(idx),长度为1(tmpLen),的字符作为最小字符串s1
2、判断从tmpLen之后的字符串是否存在与s1匹配的字符串。
若不存在,则s就是最小字符串,输出1;
若存在,则将s1与s中起始地址为1且长度为1的字符串s2比较。
若相等,则起始地址变为idx=idx+tmpLen;
若不相等,则此时最小字符串改为起始地址为0,长度为idx。
3、直到与剩余字符串都比较后,结束。
C++ 代码
#include <bits/stdc++.h>
#include <cstring>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
string str;
while(cin>>str)
{
int len = str.size(), tmpLen=1;
if(str.compare(".") == 0)
{
break;
}
int idx = str.find(str[0], 1);
tmpLen = idx;
// 当第一个字符找不到就一定整个字符串就是其最小字符串
if(str.find(str[0], 1) == std::string::npos)
{
cout<<1<<endl;
}
else
{
while(idx+tmpLen <= len)
{
// 在0-idx其中存在最小字符串为0-tmpLen;则对于整个字符串,只有可能0-idx为其最小字符串
if(str.substr(0, tmpLen).compare(str.substr(idx, tmpLen)) != 0)
{
//在整个字符串中找到0-idx的相同字符
if(str.find(str.substr(0, idx), tmpLen) != std::string::npos)
{
tmpLen = str.find(str.substr(0, idx), tmpLen);
idx = tmpLen;
}
else
{
tmpLen = len;
break;
}
}
else
idx +=tmpLen;
}
if(len % tmpLen == 0)
cout<<len/tmpLen<<endl;
else
cout<<1<<endl;
}
}
}