首页 > 试题广场 > 两个子串
[编程题]两个子串
  • 热度指数:48 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定一个字符串s, 请计算输出含有连续两个s作为子串的最短字符串。 注意两个s可能有重叠部分。例如,"ababa"含有两个"aba".

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


输出描述:
输出一个字符串,即含有连续两个s作为子串的最短字符串。
示例1

输入

abracadabra

输出

abracadabracadabra
import java.util.Arrays;
import java.util.Scanner;

public class Main{
    public static String fun(String str){
        char[] chs = str.toCharArray();
        int[] next = new int[chs.length + 1];
        next[0] = -1;
        next[1] = 0;
        int cn = 0;
        int i = 2;

        while(i < next.length){
            if(chs[i - 1] == chs[cn]){
                next[i++] = ++cn;
            }else{
                if(cn > 0){
                    cn = next[cn];
                }else{
                    next[i++] = 0;
                }
            }
        }
        int ansLen = chs.length - next[i - 1];
        char[] ans = new char[ansLen];
        for(int j = next[i - 1]; j < chs.length; j++){
            ans[j - next[i - 1]] = chs[j];
        }

        return str + new String(ans);
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = str = sc.next();
        System.out.println(fun(str));
    }

}
发表于 2019-08-12 09:00:21 回复(0)
问题是求整个串的border,
KMP可以做到O(N)。
发表于 2019-07-11 14:37:37 回复(0)
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string str;
    cin >> str;
    int n = str.length();
    for (int i = n - 1; i >= 0; --i)
    {
        string s1 = str.substr(0, i);
        string s2 = str.substr(n - i);
 
        if (s1 == s2)
        {
            // cout << s1 << "  " << s2 << endl;
            cout << str << str.substr(i);
            break;
        }
    }
    return 0;
}

发表于 2019-08-23 17:03:35 回复(0)
#include <iostream>
#include <string>
using namespace std;
int main()
{     string str,strcpyfirst,strcpylast;     int len = 0;     getline(cin,str);     for (int i = 1; i < str.size(); i++)     {         strcpyfirst = str.substr(0,i);         strcpylast = str.substr(str.size()-i, i);         if (strcpyfirst == strcpylast)         {             len = len > strcpyfirst.size() ? len : strcpyfirst.size();         }     }     strcpylast = str.substr(len, str.size() - len);     cout << str << strcpylast << endl;
}

发表于 2019-07-13 17:37:35 回复(0)