两个子串

[编程题]两个子串

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

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

输入描述:

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

输出描述:

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

示例1

输入

abracadabra

输出

abracadabracadabra

算法知识视频讲解

Java

来个大厂offer吧

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)