[12]字符串是否由子串拼接-招商银行信用卡中心2018秋

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");
}

牛客题目