重复但重叠的字符串的算法

Question

我需要编写一个方法,我给了一个字符串s,我需要返回最短的字符串,它包含s两次连续的子字符串.

然而,两次出现s可能重叠.例如,

• aba 回报 ababa
• xxxxx 回报 xxxxxx
• abracadabra 回报 abracadabracadabra

到目前为止我的代码是这样的:

import java.util.Scanner;

public class TwiceString {

    public static String getShortest(String s) {
        int index = -1, i, j = s.length() - 1;
        char[] arr = s.toCharArray();
        String res = s;

        for (i = 0; i < j; i++, j--) {
            if (arr[i] == arr[j]) {
                index = i;
            } else {
                break;
            }
        }

        if (index != -1) {
            for (i = index + 1; i <= j; i++) {
                String tmp = new String(arr, i, i);
                res = res + tmp;
            }
        } else {
            res = res + res;
        }

        return res;
    }

    public static void main(String args[]) {
        Scanner inp = new Scanner(System.in);
        System.out.println("Enter the string: ");
        String word = inp.next();

        System.out.println("The requires shortest string is " + getShortest(word));
    }
}

我知道我在算法级别而不是在编码级别可能是错误的.我的算法应该是什么？

Answer 1

使用后缀树.特别是,在构建了树之后s,转到表示整个字符串的叶子并向上走,直到看到另一个字符串结束标记.这将是最长后缀的叶子,也是前缀s.

Answer 2

一旦找到索引，即使它是 -1，您也只需将从index + 1（因为索引是最后一个匹配字符索引）到字符串末尾的子字符串附加到原始字符串。String中有一个方法可以获取这个子字符串。