TOJ4127: Root of String
2024-09-23 10:42:15
传送门: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;//如果找不到比本身小的循环节,那么自身就是循环节
}
}
最新文章
- JavaScript(js)的replace问题的解决
- 深入理解line-height与vertical-align
- CSS 问题集锦
- python实现Linux启动守护进程
- Razor入门
- HashMap的原理与实 无锁队列的实现Java HashMap的死循环 red black tree
- UITextView如何关闭键盘
- PHP 常用命令
- Wmic-linux
- HDU ACM 1068 最大独立集
- String.Join的实现
- Cracking the Coding Interview(Trees and Graphs)
- JAVA提高六:泛型
- subList ArrayList LinkedList
- 利用truffle与智能合约进行交互
- 时间mysql
- Java的学习02
- 利用sqlserver sa更改系统密码
- Oracle(四):锁
- 洛谷4294 [WC2008]游览计划——斯坦纳树