1.题目描述
给出一个非空的字符串，判断这个字符串是否是由它的一个子串进行多次首尾拼接构成的。 例如，"abcabcabc"满足条件，因为它是由"abc"首尾拼接而成的，而"abcab"则不满足条件。
- 输入描述:
非空字符串 - 输出描述:
如果字符串满足上述条件，则输出最长的满足条件的的子串；如果不满足条件，则输出false。 - 输入示例：
abcabc - 输出示例：
abc
2.题目解析
枚举遍历
1.子串长度能被字符串整除。
2.字符串的第一个字符一定是子串的第一个字符。
按照子串可能的长度遍历字符串。
3.参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int len = 1; // 重复子串长度
for(len = 1;len < s.size();++len){ // 遍历重复子串所有的可能情况
if(s.size()%len != 0) continue; // 重复子串的长度必须能被字符串s整除
int pos = 0;// 重复子串下标
int i=len;
for(i=len;i<s.size();++i){ // 假设子串长度为len，判断是否是重复子串
if(s[i] == s[pos]){
++pos;
if(pos == len){//第二次比较
pos = 0;
}
}else{
break;
}
}
if(pos == 0 && i == s.size()){
cout << s.substr(0,len) << "\n";
return 0;
}
}
printf("false\n");
}
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
for(int len=1;len<s.size();++len){
if(s.size()%len != 0) continue;
int n = s.size()/len;
string sub = s.substr(0,len);
string temp; // 构建新字符串用于比较
for(int i=0;i<n;++i){ // 把重复子串构建原串
temp = temp + sub;
}
if(temp == s){// 新串跟原串相等
cout << sub << "\n";
return 0;
}
}
cout << "false\n";
}
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
for(int len=1;len<s.size();++len){
if(s.size()%len != 0) continue;
int n = s.size()/len;
string sub = s.substr(0,len);
int i;
for(i=1;i<n;++i){
string split = s.substr(len*i,len);
if(split != sub){
break;
}
}
if(i==n){
cout << sub <<"\n";
return 0;
}
}
cout << "false\n";
}
#include <bits/stdc++.h>
using namespace std;
int main(){
string str;
cin >> str;
// 子串的长度
for(int len=1;len!=str.size();++len){// 遍历子串可能的长度
// 子串长度必须能被字符串整除
if(str.size()%len != 0) continue;
bool flag = true;
for(int i=0,j=len;j!=str.size();++i,++j){
if(str[i%len] != str[j]){// 子串与匹配字符串逐个字符比较
flag = false;
break;
}
}
if(flag){ // 找到子串
cout <<str.substr(0,len) << endl;
return 0;
}
}
cout << "false" << endl;
return 0;
}
其他解法
#include <bits/stdc++.h>
using namespace std;
int main(){
string str;
cin >> str;
int ans = 0;// 子串长度
for(ans = str.size()-1;ans>0;ans--){// 逆序遍历
int i=0;
while(str.size()%ans==0 // 字符串长度能被子串长度整除
&& i<str.size() // 遍历字符串
&& str[i] == str[i%ans]) // 字符串字符与子串字符比较
++i;
if(i==str.size()) break;
}
cout << (ans !=0 ?str.substr(0,ans):"false");
}
