传送门:http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4127

4127: Root of String
时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte

描述

The root of string S is a shortest string T such that S=TTTTT...T. That is, you can obtain S by concatenating T with itself many times.

输入

Each case has a line with one non-empty string (no more than 255 characters) over the alphabet a,b,c,...,z.

输出
For each case, output the root of the string.

样例输入

aaaaaa
ababab
abca
样例输出
a
ab
abca

思路:题意是找字符串的循环节,考虑到循环节的长度只可能是本身长度的因数,即可以从1开始,遍历因数长度的所有情况,如果能找到循环节,那么就输出,如果找不到,那么循环节就是自己本身。

分割字符串可以调用string类中的substr函数。

代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
using namespace std;
int main(){
string s;
while(cin>>s){
int a[],ans = ;
for(int i = ; i < s.size() ; i++){
if(s.size() % i == ){
a[ans++] = i;
}
}//循环节肯定是字符串长度的因数
int f = ;//记录是否找到比本身短的字符串作为 循环节
for(int i = ; i < ans; i++){//从小到大遍历因数 长度的循环节
int flag = ;//记录是否找到循环节
int k = s.size()/a[i]; //记录个数
string str[];//保存分割的字符串
for(int j = ; j < k ; j++){
int x = j * a[i];
str[j] = s.substr(x,a[i]);
}
//从x位置开始,每 a[i]个长度分割字符串,调用substr函数分割字符串
for(int j = ; j < k ; j++){
if(str[j] != str[j-]){
flag = ;break;
}
}
if(flag){
f = ;
cout<<str[]<<endl;
break;
}//遍历分割好的字符串,如果是循环节就输出
}
if(f)cout<<s<<endl;//如果找不到比本身小的循环节,那么自身就是循环节
}
}

最新文章

  1. JavaScript(js)的replace问题的解决
  2. 深入理解line-height与vertical-align
  3. CSS 问题集锦
  4. python实现Linux启动守护进程
  5. Razor入门
  6. HashMap的原理与实 无锁队列的实现Java HashMap的死循环 red black tree
  7. UITextView如何关闭键盘
  8. PHP 常用命令
  9. Wmic-linux
  10. HDU ACM 1068 最大独立集
  11. String.Join的实现
  12. Cracking the Coding Interview(Trees and Graphs)
  13. JAVA提高六:泛型
  14. subList ArrayList LinkedList
  15. 利用truffle与智能合约进行交互
  16. 时间mysql
  17. Java的学习02
  18. 利用sqlserver sa更改系统密码
  19. Oracle(四):锁
  20. 洛谷4294 [WC2008]游览计划——斯坦纳树

热门文章

  1. java对象比较==和equals的区别
  2. 没有cv2.so文件
  3. SSO单点登录、跨域重定向、跨域设置Cookie、京东单点登录实例分析
  4. guava 对集合的支持
  5. jsfl 将库中声音放置到时间轴上
  6. JSONArray
  7. 批量杀死多个进程 linux kill
  8. Linux:客户端的实现
  9. Haskell语言学习笔记(85)Async
  10. JS 实现分页打印