首页 > 试题广场 >

两个子串

[编程题]两个子串

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

给定一个字符串 s , 请计算输出含有连续两个 s 作为子串的最短字符串。注意两个 s 可能有重叠部分。例如, "ababa" 含有两个 "aba".

数据范围：输入的字符串长度满足 $1\le n \le 50 \$ ，且保证只含有小写英文字母

输入描述:

输入包括一个字符串s,字符串长度length(1 ≤ length ≤ 50),s中每个字符都是小写字母.

输出描述:

输出一个字符串,即含有连续两个s作为子串的最短字符串。

示例1

输入

abracadabra

输出

abracadabracadabra

示例2

输入

输出

aa

算法知识视频讲解

Python

华科平凡

python解法

遍历一遍，枚举出结果：

string = input()
for i in range(1, len(string) + 1):
    if string.startswith(string[i:]): # 如果后半部分字符串匹配string的起始字符串
        print(string + string[len(string) - i:])
        break

发表于 2019-03-15 22:30:15 回复(0)

Java

mignnan

import java.util.Scanner;
public class Main{
    public static void main (String[] args) {
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        String out = s + s;
        String sub = "";
        int len = s.length(); 
        int index = len;
        for(int i= len-1; i >= 1; i--) {
            sub = s.substring(i,len);
            if(s.startsWith(sub)) index = i;
        }
         if(index != len) out = s + s.substring(len-index,len);
        System.out.print(out);
    }
}

//逆序取子串，用s.startswith(s1)判断子串是不是符合条件，记录最大的子串的index，

out = s + s.substring(len-index,len);//输出有子串时的结果

编辑于 2019-04-14 11:20:03 回复(0)

pein531

假设原字符串s1有一个副本s2，先将s2的第0个字符与s1的第1个字符对齐，然后不断将字符串s2往后滑动，直到第一次两个字符串的重叠部分是相等的。如果直到s2滑到s1之后还没有相等的重叠部分，则题中所求的字符串就是把原字符串s1重复两遍。

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 s = br.readLine().trim();
        String newS = "";
        int start;
        for(start = 1; start < s.length(); start++){
            if(s.substring(start, s.length()).equals(s.substring(0, s.length() - start))){
                newS = s.substring(0, start) + s;
                break;
            }
        }
        if(start == s.length())
            System.out.println(s + s);
        else
            System.out.println(newS);
    }
}

发表于 2021-02-22 20:46:08 回复(0)

小小小智

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int lens = s.size();
    int i = 1;
    int temp=0;
    int j = 0;
    bool flag = false;
    while (i < lens)
    {
        if (s[0] != s[i])
        {
            i++;
        }
        else
        {
            temp = i;
            j = 0;
            while (s[j] == s[i])
            {
                i++;
                j++;
                if (i >= lens)
                {
                    flag = true;
                    break;
                }
            }
            if (flag == false)
{
i = temp+1;
j=0;
}
        }
    }

    string s2 = s.substr(j);
    cout << s << s2 << endl;

    system("pause");
    return 0;
}

发表于 2018-07-27 17:42:34 回复(0)

Python

raincici

s = input()
ans = 0
re = ''
for i in range(1, len(s)):
if s[i] == s[0]:
length = len(s) - i
if s[i:] == s[:length]:
ans = max(ans, len(s[i:]))
re = s + s[ans:]
print(re)

发表于 2018-09-01 20:20:41 回复(1)

0626

  #include<iostream> 
  #include<string> 
  usingnamespacestd; 
    
  intmain() 
  {string str; 
   cin>>str; 
   intlen=str.size(),loca=0; 
   for(inti=1;i<len;i++) 
       {   intk=i; 
           for(intj=0;j<=len-1;j++) 
           {   
               if(str[k]==str[j]) 
                  {   
                      k++; 
                  } 
                  else 
                  { 
                      break; 
                  } 
                if(k==len) 
                    { 
                      loca=i; 
                      break; 
                     } 
           } 
         if(loca) 
             break; 
       } 
   if(loca) 
   {  for(inti=0;i<loca;i++) 
      {cout<<str[i]; 
      } 
   cout<<str<<endl; 
  } 
   else 
       cout<<str<<str<<endl; 
        
        
        
        
      return0; 
  } 

发表于 2018-08-23 15:52:46 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s, t;
    cin>>s;
    int n=s.length(), j=0, k=-1, nxt[n+1];
    nxt[0] = -1;
    while(j<n){
        if(k==-1 || s[j]==s[k]){
            j++;
            k++;
            nxt[j] = k;
        }else
            k = nxt[k];
    }
    t = s.substr(nxt[n]);
    cout<<s+t<<endl;
    return 0;
}

发表于 2020-10-04 10:32:57 回复(0)

逃出的光线

package main

import "fmt"

func main() {
    var s string
    fmt.Scan(&s)
    length := len(s)
    if length == 1 { fmt.Println(s+s) }
    maxSameLenth := 0
    //比较字符串前i-1个字符和最后i-1个字符是否相同
    for i:=1; i<length; i++ {
        if s[:i]==s[length-i:] {
            maxSameLenth = i
        }
    }
    newString:=s+s[maxSameLenth:]
    fmt.Println(newString)
}

Golang实现

发表于 2020-09-17 11:23:00 回复(0)

C/C++

海问香12138

1.用变量i得到在1<=i<=strlen(s)范围内字符串s的前i位于后i位相同时i的最小值
2.输出字符串s的前i位
3.输出字符串s

#include <stdio.h>
#include <string.h>

char s[60];

int main()
{
	int i,j,k,flag,len;
	gets(s);
	len = strlen(s);
	for(i=1;i<len;i++)
	{
		flag = 1;
		for(j=i,k=0;j<len;j++,k++)
			if(s[j]!=s[k])
			{
				flag = 0;
				break;
			}
		if(flag)
		{
			for(j=0;j<i;j++)
				putchar(s[j]);
			puts(s);
			return 0;
		}
	}
	for(j=0;j<len;j++)
		putchar(s[j]);
	puts(s);
	return 0;
}

发表于 2019-08-22 09:15:34 回复(0)

海苔微风

需要注意的是要区别s只有一个重复字符和s字符串都不重复，因此应该让索引指向重复字符串末尾后一位，以区分0个字符重复和1个字符重复。

#include <iostream>

#include <string>
using namespace std;
unsigned long bindex(const string &s){
unsigned long i;
unsigned long index=0;
string a;
string b;
for(i=0; i<(s.size()-1);++i){
a = s.substr(0,i+1);
b = s.substr(s.size()-1-i,i+1);
if(a==b){
index = i+1;
}
}
return index;
}

int main()
{
unsigned long index;
string s;
while(cin>>s){
string ls(s);
index = bindex(s);
for(unsigned long i=index; i<s.size(); i++)
ls.append(1,s[i]);
cout << ls << endl;
}
return 0;
}

发表于 2019-04-13 16:42:46 回复(0)

Java

qiuz567

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String string = sc.next();
int l = string.length();
StringBuilder sBuilder = new StringBuilder(string+string.charAt(l-1));
for(int i=1;i<l;i++){
    String string2 = sBuilder.toString();
    if(string2.endsWith(string))break;
    sBuilder.insert(sBuilder.length()-i, string.charAt(l-1-i));
}
System.out.println(sBuilder);
    }
}

发表于 2019-03-14 20:20:50 回复(0)

向宇回桌

import java.util.*;

public class Main {
    private static final int MAX = 50005;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] in = sc.next().toCharArray();
        int n = in.length;
        StringBuilder sb = new StringBuilder();
        for (int i=1; i<n; i++) {
            boolean flag = true;
            for (int j=0; i+j<n; j++) {
                if (in[i+j] != in[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                sb.append(in, 0, i);
                sb.append(in);
                System.out.println(sb.toString());
                return;
            }
        }
        sb.append(in); sb.append(in);
        System.out.println(sb.toString());
    }
}

发表于 2019-03-02 11:25:12 回复(0)

offer菜鸟

思路：题意为判断从字符串最后一位开始算，存在多少位与从头开始的相应位数相等

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int l=s.length();    //字符串长度
    if(l==0)
        return 0;
    if(l==1)
    {
        cout<<s+s<<endl;
        return 0;
    }
    int j=1;          //截取字符个数
    int count=0;
    string temp;       //保存截取的字符
    for(int i=l-1;i>0;i--)
    {
        string s1=s.substr(i,j);      //从后往前
        string s2=s.substr(0,j);      //从前往后
        j++;

        if(s1==s2)              
        {
            temp=s2;
            count++;
        }
        else
        {
            if(j==1)       //
            {
                break;
            }
        }
    }
    if(count==0)  //表示重复的个数为零
    {
        cout<<s+s<<endl;
    }
    else
    {
        string re=s.substr(temp.length(),l-temp.length());  //截取不重复的部分
        cout<<s+re<<endl;
    }
    return 0;
}

发表于 2019-06-13 15:50:31 回复(0)

专业菜鸟i

#菜鸟出品 必属精品
s=input()
l=len(s)
for i in range(1,l+1):
    ss=s+s[-1*i:]
    if ss[-1*l:]==s:
        print(ss)
         break

发表于 2019-03-07 19:56:27 回复(1)

刘炳辰

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
    string s;
    cin >> s;
    
    //求next+1数组
    int* next = new int[s.size() + 1];
    int k = -1;
    int j = 0;
    next[0] = -1;
    while(j < s.size()){
        if(k == -1 || s[k] == s[j]) {
            j++;
            k++;
            next[j] = k;
        }
        else{
            k = next[k];
        }
    }
    //看next+1数组最后一位的值 表示前缀后缀相同字母的个数
    cout << s + s.substr(next[s.size()]) << endl;
    delete[] next;
}

发表于 2019-02-25 21:23:48 回复(0)

骞就。

#include<string>
#include<iostream>
using namespace std;
int main(){
    string s;
    while(cin>>s){
        int i=1,j=s.size()-1;
        int MaxLength=0;
        while(j>0){
            if(s.substr(0,i)==s.substr(j)) {
                MaxLength=MaxLength>i?MaxLength:i;
            }
            i++;j--;
        }
        cout<<s+s.substr(MaxLength)<<endl;
    }
}

发表于 2020-08-27 14:42:11 回复(0)

云上撷

发表于 2018-09-07 10:34:46 回复(0)

李潇羽

a = list(map(str, input().split()))
aa = a[0] + a[0]
b = len(a[0])
c = a[0]
if len(a[0]) == 1:
    print(aa)
else:
    b = []
    for i in range(len(c)):
        if c[:i] == c[len(c)-i:]:
            b.append(i)
    d = max(b)
    print(a[0][0:]+a[0][d:])

发表于 2023-09-01 19:59:33 回复(0)

小谷围做题家

package main

import (
    "fmt"
    "strings"
)

func main() {
    var s string
    fmt.Scan(&s)
    for i:=1;i<len(s);i++{
        idx:=strings.Index(s,s[i:])
        if idx==0{
            fmt.Print(s[:i]+s)
            return
        }
    }
    fmt.Print(s+s)
}

发表于 2023-03-22 13:26:45 回复(0)

Aurevive

import sys
# Rolling hash
s = sys.stdin.readline().strip('\n')
l = len(s) - 2
r = 1

base = 26
coef = lambda x: ord(x) - ord('a') + 1

head = 0
for i in range(0, len(s) - 1):
    head = head * base + coef(s[i])

tail = 0
for i in range(1, len(s)):
    tail = tail * base +coef(s[i])

most_significant = base ** (len(s) - 2)
while head != tail:
    head = (head - coef(s[l])) // base
    tail = tail - (coef(s[r]) * most_significant)
    most_significant //= base
    l -= 1
    r += 1

print(s + s[l+1:])

发表于 2020-08-27 01:52:18 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师字符串前端工程师算法工程师 PHP工程师穷举测试开发工程师京东 2018 Java工程师

上传者：小小

难度：

46条回答 66收藏 10252浏览

通过挑战的用户

查看代码

这个下午很懒

2022-09-09 09:32:11
一世白纸

2022-09-08 22:32:53
牛客47032...

2022-09-03 16:33:57
牛客25879...

2022-09-03 08:40:38
不掉头发程序员

2022-08-26 20:41:57

两个子串

输入描述:

输出描述:

输入

输出

输入

输出

python解法

1.用变量i得到在1<=i<=strlen(s)范围内字符串s的前i位于后i位相同时i的最小值
2.输出字符串s的前i位
3.输出字符串s

问题信息

热门推荐

通过挑战的用户

相关试题

两个子串

输入描述:

输出描述:

输入

输出

输入

输出

python解法

1.用变量i得到在1<=i<=strlen(s)范围内字符串s的前i位于后i位相同时i的最小值 2.输出字符串s的前i位 3.输出字符串s

问题信息

热门推荐

通过挑战的用户

相关试题

1.用变量i得到在1<=i<=strlen(s)范围内字符串s的前i位于后i位相同时i的最小值
2.输出字符串s的前i位
3.输出字符串s