【题目典例】UVA455 周期串 Periodic Strings

博主： Fivk
发布时间：2021 年 07 月 19 日
1276 次浏览
暂无评论
494字数
分类：题目典例

![](https://blog.fivk.cn/usr/uploads/2021/07/2462951403.png)

## 题意翻译

如果一个字符串可以由某个长度为k的字符串重复多次得到，则称该串**以k**为周期 。例如，**abcabcabcabc以****3** 为周期（注意，它也以**6** 和**1****2** 为周期）。

输入一个长度不超过**80**的字符串，输出其最小周期。

## 输入输出样例

**输入样例**

```in
1
HoHoHo
```

**输出样例**

```out
2
```

### 方法1：暴力穷举

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,len,ans;
string s;

bool test(int T) 
{
	for(int i=0;i+T<len;i++)
	{
		if(s[i]!=s[i+T])
			return false;
	}
	return true;
}

int main()
{
	cin>>n;
	while(n--)
	{
		cin>>s;
		len=s.length();
		ans=len;
		for(int T=1;T<len;T++)
		{
			if(len%T==0&&test(T))
			{
				ans=T;
				break;
			}
		}
		cout<<ans<<endl;
		if(n)
			cout<<endl;
	}
	return 0;
 } 
```

### 方法二：string中的+号运算符

```cpp
#include<iostream>
#include<string>
using namespace std;
int main(){
	string s,k;
    //s是原来字符串，k是重复的字符串
	int n;
	cin>>n;
	while(n--){
		cin>>s;
		k="";//别忘了初始化！
		for(int i=0;i<s.length();i++){
			k+=s[i];//在k的后面加上s中的下一项
			if(s.length()%k.length()==0){//如果能整除（就是重复可以正好凑齐）
				int t=s.length()/k.length();
                //t是循环几次
				string k2;//k2用来比较
				for(int j=0;j<t;j++){
					k2+=k;//k2一直累加到长度与s相同
				}
				if(k2==s){//判断是否相同
					cout<<k.length()<<endl;
                    //输出长度
					i=s.length();
                    //跳出循环的搞笑方法
					if(n)cout<<endl;
                    //自己看格式
				}
			}
		}
	}
	return 0;
}
```

最后修改：2021 年 09 月 12 日