给出一个非空的字符串，判断这个字符串是否是由它的一个子串进行多次首尾拼接构成的。
例如，"abcabcabc"满足条件，因为它是由"abc"首尾拼接而成的，而"abcab"则不满足条件。
[编程题]字符串是否由子串拼接
#include <iostream>
using namespace std;
int main()
{
string str;
cin>>str;
int fPos = 0,rPos =1,sLen = 1;
int len = str.size();
for(;rPos < len ; rPos++ ){
if(str[fPos] == str[rPos]){//如果匹配，则fPos++
fPos++;
}else{
sLen = rPos+1;//如果不匹配，则认为0~rPos之间为子串，其长度为rPos+1
fPos = 0;
}
if(fPos == sLen && rPos != len -1){
fPos = 0;//如果匹配到当前子串的结尾，则从子串开头匹配。
}
}
if(fPos != sLen ){
cout<<"false"<<endl;
}else{
cout<<str.substr(0,sLen)<<endl;
}
return 0;
}
核心思想是一旦匹配失败，就认为当前 0和 rPos之间的字符串为组成整串的子串。
空间复杂度O(1),时间复杂度O(n);
编辑于 2018-10-05 16:45:58
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main() {
string s; cin >> s;
int n = s.length();
int ans = 0;
for (int i=1; i<=n/2; i++) {
if (n % i != 0) { continue; }
bool flag = true;
for (int j=0; j<n; j++) {
if (s[j] != s[j%i]) {
flag = false;
break;
}
}
if (flag) ans = i;
}
if (ans == 0) cout << "false" << endl;
else {
cout << s.substr(0, ans) << endl;
}
return 0;
}
发表于 2019-04-09 16:26:39
回复(0)
string=input()
flag=0
for i in range(len(string)): #遍历整个字符
string_sub=string[0:i] #从前往后的取子字符
cishu=string.count(string_sub) #计算这个子字符在总字符中的出现次数
if cishu*len(string_sub)==len(string): #如果子字符出现的次数乘上子字符长度等于总的字符长度
print(string_sub)
flag=1 #这个标记表明找到了对应的字符串
else:
pass
if flag==0:
print('false')
flag=0
for i in range(len(string)): #遍历整个字符
string_sub=string[0:i] #从前往后的取子字符
cishu=string.count(string_sub) #计算这个子字符在总字符中的出现次数
if cishu*len(string_sub)==len(string): #如果子字符出现的次数乘上子字符长度等于总的字符长度
print(string_sub)
flag=1 #这个标记表明找到了对应的字符串
else:
pass
if flag==0:
print('false')
发表于 2018-08-25 15:06:57
回复(0)
一个子串要重复，那它起码要重复两次，所以如果存在这样的子串，最长也就是原始串一半的长度。因此从0位置开始截取子串，穷举长度从1~n/2+1的所有子串，看重复之后能否变成原始串。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine().trim();
int n = str.length();
String res = "false";
for(int end = 1; end <= n / 2 + 1; end++){
int times = n / end; // 重复次数
if(times * end == n && str.equals(repeat(str.substring(0, end), times))){
res = str.substring(0, end);
}
}
System.out.println(res);
}
private static String repeat(String s, int times) {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < times; i++){
sb.append(s);
}
return sb.toString();
}
}
发表于 2022-01-18 12:37:43
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
int n=s.length(), p=0, q=1, l=1;
while(q < n){
if(s[p] == s[q])
p++;
else{
l = q + 1;
p = 0;
}
if(p==l && q!=n-1)
p = 0;
q++;
}
if(p==l)
cout<<s.substr(0, l)<<endl;
else
puts("false");
return 0;
}
发表于 2020-10-27 00:33:55
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
String base = new Scanner(System.in).next().trim();
char head = base.charAt(0);
int index = base.indexOf(head, 1);
String result = null;
while (index != -1 && index <= (base.length() / 2)) {
String tmp = base.substring(0, index);
if (base.replaceAll(tmp, "").length() == 0) {
result = tmp;
}
index = base.indexOf(head, index + 1);
}
System.out.println(result != null ? result : false);
}
}
发表于 2019-04-01 15:32:15
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
for (int i = 1; i<=s.length()/2; i++)
{
String sub = s.substring(0,i);
String str = s;
str = str.replace(sub,"");
if (str.isEmpty())
{
System.out.println(sub);
return;
}
}
System.out.println("false");
}
}
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
for (int i = 1; i<=s.length()/2; i++)
{
String sub = s.substring(0,i);
String str = s;
str = str.replace(sub,"");
if (str.isEmpty())
{
System.out.println(sub);
return;
}
}
System.out.println("false");
}
}
发表于 2018-09-07 22:50:03
回复(1)
import java.util.Scanner;
public class Main_09 {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
while(s.hasNext()){
String str = s.next();
int start=0;
int stop=str.length()-1;
//不能输出本身，所以至少有两个
int mid = (start+stop)/2;
//标记是否发现符合要求的子串
boolean flag = false;
for(int i=start;i<=mid;i++){
if(findsame(str,0,i)){
System.out.println(str.substring(0,i+1));
flag = true;
break;
};
}
if(!flag){
System.out.println("false");
}
}
}
public static boolean findsame(String str,int start,int stop){
boolean flag = true;
int length = stop-start+1;
//如果不整除，则一定不是符合的子串
if(str.length()%length==0){
for(int i=0;i<str.length()/length-1;i++){
if(!str.substring(start,stop+1).equals(str.substring(start+(i+1)*length,stop+length*(i+1)+1))){
flag = false;
}
}
}else {
flag = false;
}
return flag;
}
}
发表于 2018-08-18 20:30:42
回复(0)
import java.util.*;
public class Main{
public static void isExist(String str) {
String n = str;
//字符串第一个字符
String m=n.substring(0, 1);
//查询第一个字符第二次出现的位置
int start2=n.indexOf(m,1);
if(start2<0){
System.out.println("false"); //若只有不重复的字符串，返回false
}else{
//查询第一个字符最后出现的位置
int end1=n.lastIndexOf(m);
boolean flag = false;
while(start2<=end1&&start2!=-1) {
String substr=n.substring(0,start2);
//若输入字符串长度不是重复字符串长度的倍数，返回false
if(n.length()%substr.length()==0){
boolean find = true;
for(int i=start2;i<n.length();i=i+start2){
//查看 母字符串 是否是 由子字符串 循环拼接而成
if(!n.substring(i,i+start2).contains(n.substring(0,start2))){
find = false;
//System.out.println("false");
break;
}
}
//如果该字符串满足要求 则标记找到
if(find) {
flag = true;
System.out.println(n.substring(0,start2));
}
}
//找到合适的子字符串 跳出循环
if(flag) break;
else {
start2 = n.indexOf(m,start2+1);
}
}
if(!flag) System.out.println("false");
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//System.out.println("请输入一个字符串");
while(scanner.hasNext()) {
String str = scanner.nextLine();
isExist(str);
}
}
}
发表于 2018-08-18 11:41:53
回复(0)
package MerchantsBank;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class IsStitchBySubString {
static String p(String str) {
int i=0,j=1;
//找到第一个可能的子串，str[j]与str[0]相同
for(;j<str.length();j++) {
if(str.charAt(0)==str.charAt(j))
break;
}
int k=j;
while(k<str.length()) {
for(i=0,j=k;i<str.length()&&j<str.length();i++,j++) {
if(i==k)
i=0;
if(str.charAt(i)!=str.charAt(j))
break;
}
if(j==str.length()&&i==k)
return str.substring(0, k);
else
k++;//如果不是子串，结束位置往后移动。
}
return "false";
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
// String str="abcabc";
BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
String str = scanner.readLine();
String res=p(str);
System.out.println(res);
}
}
发表于 2018-08-18 21:38:12
回复(0)
def func(x): a=set(x) l=len(a) b=[] for i in range(l): b.append(x[i]) for i in range(len(x)): c=i%l if x[i]==b[c]: continue else: return False return True
发表于 2018-08-17 09:23:45
回复(0)
import java.util.Scanner;
public class test {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
System.out.println("请输入一个字符串");
String n=input.nextLine();
String m=n.substring(0, 1); //字符串第一个字符 int a=n.indexOf(m,1); //查询第一个字符第二次出现的位置 if(a<0){
System.out.println("false"); //若只有不重复的字符串，返回false }else{
String b=n.substring(0,a); if(n.length()%b.length()!=0){
System.out.println("false"); //若输入字符串长度不是重复字符串长度的倍数，返回false }else{
boolean flag=true; for(int i=a;i<n.length();i=i+a){ if(!n.substring(i,i+a).contains(n.substring(0,a))){
System.out.println("false");
flag=false; break;
}
} if(flag){
System.out.println("最长的字符串为"+n.substring(0,a));
}
}
}
}
}
发表于 2018-08-15 11:39:18
回复(1)
importjava.util.Scanner;public class Main {public static void main(String[] args){Scanner sc = new Scanner(System.in);String str = sc.nextLine();int i = str.length() / 2; //最长也不过是原字符串长度的一半for(; i >= 0; i--){String sub = str.substring(0,i);//每次截取前i个字符串if(str.replaceAll(sub,"").length()==0){//利用正则表达式，替换原字符串的内容，如果最后为空，说明可以被完全替换，所以是最长字串System.out.println(sub);return;}}System.out.println(false);}}
发表于 2018-08-31 11:21:47
回复(4)
这是一个很基础的字符串处理的题目，我最开始的时候一直在纠结要是全部都是相同的字符那么是字符串的长度还是长度的一半，后来wa了一发才试出来原来最大就是原来字符串的一半，于是就非常简单了，利用string的find和erase就可以很轻易的做到，循环从二分一直字符串长度开始，利用find看是否跟原字符串的第0个位置的匹配，要是匹配就用erase函数擦除，最后判断原字符串是否为空即可。代码如下
#include<bits/stdc++.h>
using namespace std;
int main(){
string str;
cin>>str;
int len = str.size()/2;
for(;len>0;len--){
string temp = str.substr(0,len);
string tempAll = str;
while(tempAll.find(temp)==0){
tempAll.erase(0,len);
}
if(tempAll.size()==0){
cout<<temp<<endl;
return 0;
}
}
cout<<"false"<<endl;
return 0;
}
发表于 2019-02-14 15:42:43
回复(1)
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String result = "";
String[] allResult = new String[s.length()];
int count = 0;
for(int i=0;i<s.length()/2;i++){
if(isSubString(s,s.substring(0,i+1))){
allResult[count] = s.substring(0,i+1);
count ++;
}
}
if(allResult[0]!=null){
System.out.print(allResult[0]);
}else{
System.out.print(false);
}
}
public static boolean isSubString(String s,String subStr){
if((subStr+s).equals(s+subStr)){
return true;
}
return false;
}
}
发表于 2020-06-20 12:03:09
回复(0)
没有使用字符串替换 replaceAll 的操作，单纯的循环判断，写得可能有些冗余
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int len = s.length();
StringBuilder sb = new StringBuilder();
sb.append(s.charAt(0));
boolean isSubstring = true;
int findCnt = 0;
for (int i = 1; i <= len / 2; i++) {
if (s.charAt(i) == sb.charAt(0)) {
int cnt = 1;
while (cnt != sb.length()) {
if (s.charAt(cnt) != s.charAt(cnt)) {
break;
}
cnt++;
}
if (cnt == sb.length()) {//是子串
for (int j = i; j < len; j++) {
if (s.charAt(j) != sb.charAt(j % sb.length())) {
isSubstring = false;
break;
}
}
break;
} else {
sb.append(s.charAt(i));
}
} else {
sb.append(s.charAt(i));
}
findCnt++;
}
if (isSubstring && findCnt != len / 2) {
System.out.println(sb.toString());
} else {
System.out.println("false");
}
}
}
发表于 2020-04-08 16:45:48
回复(0)
strs = input()
str_find = strs
index = strs.index(strs[-1])
while index <= len(strs) / 2:
str_find = str_find.replace(strs[:index+1], '')
if len(str_find) == 0:
print(strs[:index+1])
exit()
else:
index = strs.index(strs[-1], index+1)
str_find = strs
print('false')
str_find = strs
index = strs.index(strs[-1])
while index <= len(strs) / 2:
str_find = str_find.replace(strs[:index+1], '')
if len(str_find) == 0:
print(strs[:index+1])
exit()
else:
index = strs.index(strs[-1], index+1)
str_find = strs
print('false')
发表于 2020-04-08 15:58:09
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String res = "";
for(int i = 0;i < s.length() / 2;i++){
StringBuilder sb = new StringBuilder("");
String sub = s.substring(0,i + 1);
while(sb.length() < s.length()){
sb.append(sub);
}
if(sb.toString().equals(s) && (sub.length() > res.length()))
res = sub;
}
System.out.println(res == "" ? "false" : res);
}
}
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String res = "";
for(int i = 0;i < s.length() / 2;i++){
StringBuilder sb = new StringBuilder("");
String sub = s.substring(0,i + 1);
while(sb.length() < s.length()){
sb.append(sub);
}
if(sb.toString().equals(s) && (sub.length() > res.length()))
res = sub;
}
System.out.println(res == "" ? "false" : res);
}
}
发表于 2020-03-20 12:30:20
回复(0)
import java.util.Scanner;
/**
* 给出一个非空的字符串，判断这个字符串是否是由它的一个子串进行多次首尾拼接构成的。
* 例如，"abcabcabc"满足条件，因为它是由"abc"首尾拼接而成的，而"abcab"则不满足条件。
*/
public class Main {
/**
* 思路：等分
* @param str
* @return
*/
public static String duplicate (String str){
//初始化等分份数
int subNum = 2;
int len = str.length();
while (len / subNum > 0){
if (len % subNum != 0){
subNum++;
continue;
}else {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < subNum; i++) {
sb.append(str.substring(0, len / subNum));
}
if (str.equals(sb.toString())){
return str.substring(0 , len / subNum );
}
subNum++;
}
}
return "false";
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
String duplicate = duplicate(s);
System.out.println(duplicate);
}
}
编辑于 2019-10-11 21:06:49
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner read=new Scanner(System.in);
String s=read.next(); read.close();
if(s.length()<2){
System.out.println(s);
return ;
}
//时间复杂度O(n),可匹配正则字符
int begin=0,end=0,cur=1; //begin/end记录当前子串起始终止位置，cur记录当前考察的原字符串下标
while(cur<s.length()) {
int temp=begin;
while(s.charAt(cur)==s.charAt(temp)) {
if(temp==end) { //如果考察到子串最后一个，即比如a(begin)bc(end)abc(cur)abc
begin=end+1; //改变begin/end/cur的值为： abca(begin)bc(end)a(cur)bc
end=cur;
temp=begin-1;
}cur++;temp++;
if(cur==s.length()) {//如果cur变成了最后一个， 当begin==0，输出false，否则输出子串
if(begin==0)break;
//System.out.println(s.substring(begin)); //最短匹配
//尽管题目要求输出最长匹配，这个题的测试用例输出最短也会通过
int len=end-begin+1,m=2;
while(!(s.length()%m==0&&s.length()/m%len==0)) m++;
int time=s.length()/m/len;
while(time-->0)
System.out.print(s.substring(begin)); //最长匹配
System.out.println();
return ;
}
}
begin=0;
end=cur++;
}System.out.println("false");
}
}
发表于 2019-09-05 10:39:51
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-04 19:29:21
-
2023-01-09 18:34:13
-
2022-10-25 14:46:53 -
2022-09-26 20:13:34 -
2022-09-26 20:02:11
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
