首页 > 试题广场 >

字符串是否由子串拼接

[编程题]字符串是否由子串拼接

热度指数：2142 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个非空的字符串，判断这个字符串是否是由它的一个子串进行多次首尾拼接构成的。

例如，"abcabcabc"满足条件，因为它是由"abc"首尾拼接而成的，而"abcab"则不满足条件。

输入描述:

非空字符串

输出描述:

如果字符串满足上述条件，则输出最长的满足条件的的子串；如果不满足条件，则输出false。

示例1

输入

abcabc

输出

abc

算法知识视频讲解

C/C++

西安墨菲特

//利用KMP算法
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    string& repeatedSubstringPattern(string s) {
    int l = s.length();
    vector<int> next(l);
    string res;
    next[0] = -1;
    int i, j = -1;
    for (i = 1; i < l; i++) {
        while (j >= 0 && s[i] != s[j + 1]) {
            j = next[j];
    }
    if (s[i] == s[j + 1]) {
        j++;
    }
    next[i] = j;
    }
    int lenSub = l - 1 - next[l - 1];
    if(lenSub != l && l % lenSub ==0)
    {
        for(int i=0;i<lenSub;++i)
            res += s[i];
    }
    return res;
    }
};
int main() {
    string str;
    while (cin >> str) {
    cout<<Solution().repeatedSubstringPattern(str);
}
return 0;
}

编辑于 2019-04-12 11:22:14 回复(1)

liaoming

#include <iostream>
#include <string>
 
using namespace std;
 
string process(const string & str) {
    for (int i = 2; i <= str.size(); ++i) {
        if (str.size() % i == 0) {
            int sub_len = str.size() / i;
            string sub_str = str.substr(0, sub_len);
            // 要求各字串都相等
            int j = 0;
            for (j = sub_len; j < str.size(); j += sub_len) {
                if (sub_str != str.substr(j, sub_len)) {
                    break;
                }
            }
            if (j >= str.size()) {
                return sub_str;
            }
        }
    }
    return "";
}
 
int main() {
    string str;
    while (cin >> str) {
        string res = process(str);
        if (res.size() < 1) {
            cout << "false" << endl;
        } else {
            cout << res << endl;
        }
    }
    return 0;
}

编辑于 2018-08-10 08:22:59 回复(2)

S1mpeboy

编程语言：python3

思路：

从最长的二等分开始查找，用等分后的字符串tmp拼接成新的字符串tmp*flag与原字符串S进行比较，如果相等，返回这个字符串tmp，
如果不相等进行三等分以此类推，如果直至n等分(n=字符串A长度)都不能满足，输出false。

def main():
    s = input("").strip()
    return find(s)
def find(s):
    if len(s) == 1:
        return 'false'
    else:
        #等分份数
        flag = 2
        while(flag<=len(s)):
            #整数除，向下取整，方便截取tmp
            n = len(s)//flag
            tmp = s[0:n]
            #判断拼接后字符串是否等于原字符串
            if tmp*flag == s:
                return tmp
            else:
                flag += 1
        return 'false'
if __name__ == '__main__':
    print(main())

发表于 2021-03-27 16:26:20 回复(0)

bettermin

def copy(s):
    if len(s)<2:
        return s
    res = []
    for i in range(1,len(s)//2+1):
        ss = s[:i]
        if is_copy(ss,s):
            res.append(ss)
    return res if res else 'false'
 
def is_copy(ss,s):
    i = len(s)//len(ss)
    if len(s)%len(ss) != 0:
        return False
    if ss*i == s:
        return True
    else:
        return False
     
s = input()
print(copy(s))

发表于 2020-03-26 18:44:26 回复(1)

阿里云智能招聘

 def judge(s):
    l = len(s)
    for i in range(1, l / 2 + 1):
        if l % i == 0:
            substr_len = l / i
            sub_str = s[:i]
            for k in range(1, substr_len+1):
                if sub_str != s[k*i : i*(k+1)]:
                    break
            if k == substr_len :
                return s[:i]
    return 'false'


if __name__ == '__main__':
    raw_str = raw_input()
    print (judge(raw_str))

发表于 2018-08-10 22:46:39 回复(0)

shijiacheng

import java.util.Scanner;

/**
 * 字符串是否由子串拼接
 * 给出一个非空的字符串，判断这个字符串是否是由它的一个子串进行多次首尾拼接构成的。
 * 例如，"abcabcabc"满足条件，因为它是由"abc"首尾拼接而成的，而"abcab"则不满足条件。
 * 输入描述:
 * 非空字符串
 * 输出描述:
 * 如果字符串满足上述条件，则输出最长的满足条件的的子串；如果不满足条件，则输出false。
 * 输入例子1:
 * abcabc
 * 输出例子1:
 * abc
 *
 * @author shijiacheng
 */
public class StringIsMakeUpSubstring {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        int length = str.length();
        String result = "";
        for (int i = 1; i <= length / 2; i++) {
            if (length % 1 == 0) {
                String sub = str.substring(0, i);
                String temp = "";
                for (int j = 1; j <= length / i; j++) {
                    temp += sub;
                }
                if (temp.equals(str)) {
                    result = sub;
                }
            }

        }
        if (result.equals("")) {
            System.out.println(false);
        } else {
            System.out.println(result);
        }
    }

}

发表于 2018-08-14 23:25:33 回复(1)

鱼忘七秒

var str = readline();
var len = str.length;
var mid = parseInt((len - 1)/2);
var result = false;
for (var i = mid; i >= 0; i--) {
     if (len%(i+1) == 0){
        var num = len/(i+1);
        var subStr = str.slice(0,i+1);
        if (subStr.repeat(num) === str) {
            result = subStr;
            break;
        }
    }
}
print(result);

发表于 2019-09-05 00:23:12 回复(0)

高手·扫地僧

第一步得到子串第二步按子串的长度取依次去原串的子串，进行比对，如果符合则继续取，否则执行第三步第三步不符合的情况有：得到的子串长度不够（原串需是子串的倍数），得到的子串和第一步得到的子串不想等

发表于 2023-03-07 07:31:35 回复(0)

牛客441582696号

#include<stdio.h>
#include<string.h>
int main()
{
char s[100],s_son[100];
int son_length,i,j,s_length,group,state=0,success=0;
    gets(s);
    s_length=strlen(s);
    for(son_length=1;son_length<=s_length/2;son_length++)
{
if (s_length%son_length!=0)
    {continue;}
else
{
    group=s_length/son_length;
    for(j=0;j<son_length;j++)
            for(i=1;i<group;i++)
            {
                if(s[j]!=s[j+i*son_length])
                    {break;}
                else {state++;s_son[j]=s[j];}
            }
    if(state==son_length*(group-1))
        {success=1;break;}
    state=0;
}
}

if(success==1)
    for(i=0;i<son_length;i++)
{
    printf("%c",s_son[i]);
}
else printf("false");

}

发表于 2022-03-10 21:16:16 回复(0)

伍粟

剑指剑指 Offer 14- I. 剪绳子(C++) 贪心算法

https://blog.csdn.net/qq_30457077/article/details/114733448

发表于 2021-07-08 19:41:10 回复(0)

JavaScript

顺手牵yang

var arr = readline()
print(strPin(arr))
function strPin(arr){
var n= arr.length
var mid = arr.length/2
var result = false
for(var i = 0 ; i<mid; i++){
if(n%(i+1)==0){
var subStr = arr.slice(0,i+1)
if (subStr.repeat(n/(i+1)) === arr){
result = subStr
break
}
}

}
return result
}

发表于 2021-03-31 10:43:45 回复(0)

sunxun

剪枝+循环移动比较。如果一个序列有周期的话，循环移动一个周期之后是和原序列相同的。

#include <iostream> using namespace std; bool foo(const string &str, int n) { int L = str.size(); for (int i = 0; i < L; i++) { if(str[i] != str[(i+n)%L])return false; } return true; } int main() { string s; cin >> s; int L = s.size(); int n = L / 2; int i = 1; for (; i <= n; i++) { if(L % i == 0 && foo(s, i)) { cout << s.substr(0,i); break; } } if (i > n)cout << "false"; return 0; }

发表于 2020-08-07 15:54:47 回复(0)

苹果头

#include<iostream>
(720)#include<string>
#include<stdlib.h>

using namespace std;

string find(const string& str)
{
	string final_str = "";
	string sub_str;
	for (int i = 1; i < str.size(); i++)
	{
		if (str.size() % i != 0)
			continue;
		sub_str = str.substr(0, i);
		string temp_str;
		for (int times = 1; times <= str.size() / i; times++)
		{
			temp_str += sub_str;
		}
		if (temp_str != str)
			continue;
		if (i >= final_str.size())
		{
			final_str = sub_str;
		}
	}
	return final_str;
}

int main()
{
	string str;
	string res;
	while (cin >> str)
	{
		res = find(str);
		if (res.size() < 1)
			cout << "false" << endl;
		else
			cout << res << endl;
	}
	system("PAUSE");
	return 0;
}

发表于 2020-03-26 22:23:02 回复(0)

小白鸟

/*
遍历法，遍历子串长度从1到n/2，选择满足要求的最大子串。
*/


#include<iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    getline(cin,s);
    string res = "";
    for(int i = 0; i<s.length()/2; i++)
    {
        //子串的长度应该可以被字符串长度整除。
        if(s.length()%(i+1) == 0)
        {
            int real = 1;
            for(int j = i+1; j<s.length();j++)
            {
                int temp = ((j+1)%(i+1)-1<0)?i:((j+1)%(i+1)-1) ;                
                if(s[temp] != s[j])
                {
                    real = 0;
                    break; 
                }  
            }
            if(real == 1)
                res = s.substr(0,i+1);
        }        
    }
    if(res == "")
        cout<<"false"<<endl;
    else
        cout<<res<<endl;
    return 0;
}

发表于 2019-09-15 00:21:43 回复(0)

慢热的长颈鹿

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
using namespace std;

bool fun(string out, string s)
{
	int out_len = out.length();
	int s_len = s.length();
	int pos = out.find(s);
	if (pos != 0) return false;
	for (int i = 0; i < out_len; i++)
	{
		if (i%s_len == 0)
		{
			string tmp = out.substr(i);
			int tmp_pos = tmp.find(s);
			if (tmp_pos != 0)
			{
				return false;
			}
		}
	}
	
	return true;
}

string min_str(string s,int k)
{
	int s_len = s.length();
	string min = s.substr(0,1);
	for (int i = 1; i < s_len; i++)
	{
		min = s.substr(0, i);
		int tmp_pos = min.find(s[i]);
		if (tmp_pos == 0)break;
	}
	string new_s = min;
	if (k == 1) return new_s;
	
	for (int i = 0; i < k-1; i++)
	{
		new_s = new_s + min;
	}

	return new_s;
}

int main()
{

	string s;
	cin >> s;
	int k = 1;
	string res = "false";
	while (true)
	{
		string mins = min_str(s,k);
		k += 1;
		if (mins.length() > s.length()/2) break;
		bool match = fun(s, mins);
		if (match == true) res = mins;
		else continue;
	}
	cout << res << endl;
	system("pause");
	return 0;


}

发表于 2019-09-03 16:42:00 回复(0)

叭叭叭

  #include<iostream> 
  #include<string> 
  #include <string.h> 
  using namespace std; 
    
  int main() 
  { 
  char str[10000]; 
      cin >> str; 
      int N = strlen(str); 
      char strcur[10000]; 
      for (int i = 1;i <N;i++) 
      { 
          bool beuq = true; 
          char str0[10000]; 
          char strx[10000]; 
          strncpy(str0, str, i); 
          str0[i] = '\0'; 
          if (N%i!=0) 
              continue; 
          for (int j= 1;j*i<N;j++) 
          { 
              int stride = strlen(str0); 
              strncpy(strx, str + j*stride, i); 
              strx[i] = '\0'; 
              int equ = strcmp(str0, strx); 
              if (equ != 0) 
              { 
                  beuq = false; 
                  break; 
              } 
          } 
          if (beuq) 
          { 
              strncpy(strcur, str, i); 
              strcur[i] = '\0'; 
          } 
      } 
      if (strlen(strcur)==0) 
      { 
          cout <<"false"; 
          return 0; 
      } 
      cout << strcur << endl; 
  } 

发表于 2018-09-07 22:52:30 回复(0)

鬼祟

import java.util.*;
public class Main1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int n = s.length();
        String ac = "" ;
        boolean flag = false;
        for(int i=n/2;i>=1;i--){
            String str = s.substring(0, i);
            String res = "";
            for(int j=0;j<n/i;j++){
                res += str;
            }
            if(res.equals(s)){
                ac = str;
                flag = true;
                break;
            }

        }
        if(flag){
            System.out.println(ac);
        }else{
            System.out.println("false");
        }

    }

}

发表于 2018-08-29 10:59:58 回复(0)

NOx的烦恼


	deffunc(s):



	    lenth=len(s)



	    i=0



	    j=1



	    p=0



	    whilej<=lenth-1:



	        if s[i]==s[j]:



	            if p==0:



	              p=j



	            i+=1



	            j+=1



	        else:



	            if p!=0:



	                i=0



	                p=0



	            else:



	                i=0



	                p=0



	                j=j+1



	    ifj==lenth and p!=0and lenth%p == 0:



	        returns[0:p]



	    else:



	        return'false'



	 



	print(func(input()))

发表于 2018-08-25 17:12:28 回复(0)

小鱼骆驼

  #include <cstdio> 
  #include <string.h> 
  #include <cstdlib> 
  void FindLength(char*  str1, int len){ 
      int i = 0, j = 0, k = 0, count = 0, result = 0; 
      bool flag = true; 
      for(i = 1; i <= len / 2; i++){ 
          if(len%i != 0){ 
              continue; 
          } 
          count = len / i; 
          flag = true; 
          for(j = 0; j < i; j++){ 
              k = 0; 
              while(k < (count - 1)*i){ 
                  if(str1[k] == str1[k + i]){ 
                      k = k + i; 
                  } 
                  else{ 
                      flag = false; 
                      break; 
                  } 
              } 
              if(flag == false){ 
                  break; 
              } 
          } 
          if(j >= i){ 
              result = i; 
          } 
    
      } 
      if(result == 0){ 
          printf("false"); 
          return; 
      } 
      for(j = 0; j < result; j++){ 
          printf("%c", str1[j]); 
      } 
  } 
  int main(){ 
      charstr1[100]; 
      scanf("%s",str1); 
      intlen = strlen(str1); 
      FindLength(str1, len); 
      system("pause"); 
      return0; 
  } 

发表于 2018-08-24 14:14:21 回复(0)

听雪歌有offer

import java.util.Scanner;

public class Main {

    public static void  main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        boolean flag = false;
        for(int i = s.length()/2;i>0;i--) {
            if(s.length()%i != 0) continue;
            else if(compare(s,i)) {
                flag = true;
                System.out.println(s.substring(0,i));
                break;
            }
        }
        if(!flag) System.out.println("false");
    }

    public static boolean compare(String s,int n) {
        String str = s.substring(0,n);
        for(int i = n;i<s.length();i+=n) {
            if(!s.substring(i,i+n).equals(str)) return false;
        }
        return true;
    }
}

发表于 2018-08-13 11:30:13 回复(0)