洛谷-UVA455 周期串 Periodic Strings

雨点打透心脏的1/2处 2023-06-13 09:39 20阅读 0赞

![format_png][]

## 输入格式 ##

![format_png 1][]

## 输出格式 ##

![format_png 2][]

## 题意翻译 ##

如果一个字符串可以由某个长度为kk 的字符串重复多次得到，则称该串**以kk 为周期**。例如，abcabcabcabcabcabcabcabc以33 为周期（注意，它也以66 和1212 为周期）。

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

## 输入输出样例 ##

**输入 \#1**复制

1
    HoHoHo

**输出 \#1**复制

#include <bits/stdc++.h>
    using namespace std;
    int main(){
    		int n;
    		cin>>n;//测试用例个数
    		bool flag; 
    		string s;
    		while(n--){			
    			cin>>s;	
    			int len=s.size();
    			int TT =len;//周期初始为整个字符串(没有重复的周期)
    			for(int T=1;T<80;T++){
    				flag=true;
    				for(int i=0;i+T<len;i++){
    					if(s[i]!=s[i+T]){
    						flag=false;
    						break;
    					} 
    				}
    				if(len%T==0&&flag==true){//确保长度是周期的倍数！！ 
    					TT=T;						
    					break;			
    				}
    			}		
    			cout<<TT<<endl;	
    			if(n){//n-1个数据都有空行，最后一个没有空行 
    				cout<<endl; 
    			}
    		}
    		return 0;
    	}

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTQ1NS8wZjJjOTUxZGRkNGI4NDcwZjk4YzNiNTJjZGMzYzAzYzZmOTExNTcxLnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTQ1NS8zNGQ3MDZjMjYyZGU5N2E1NWRjYjM2MjJmN2M5NTEzMmE1NTAyOGMzLnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTQ1NS80NzA1OTcyNDE3Y2ZjYjhjMzFjMjVlNzM3NjJlOTI2NzhlMmVmZThiLnBuZw?x-oss-process=image/format,png