算法的重复，但重复的字符串 [英] Algorithm for duplicated but overlapping strings

问题描述

我需要写在这里，我给一个字符串取值的方法，我需要返回包含取值为连续的子两次。

I need to write a method where I'm given a string s and I need to return the shortest string which contains s as a contiguous substring twice.

不过两次出现取值可能会重叠。例如，

However two occurrences of s may overlap. For example,

• ABA 返回巴
• XXXXX 返回 XXXXXX
• 胡言乱语返回 abracadabracadabra

• aba returns ababa
• xxxxx returns xxxxxx
• abracadabra returns abracadabracadabra

我的code到目前为止是这样的：

My code so far is this:

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));
    }
}

我知道我可能是错在算法级，而不是在编码水平。应该是什么我的算法？

I know I'm probably wrong at the algorithmic level rather than at the coding level. What should be my algorithm?

推荐答案

使用后缀树。特别是，当你建造的树取值，去叶重presenting整串走，直到你看到另一端的字符串标记。这将是最长的后缀的叶子，这也是对 s的preFIX 。

Use a suffix tree. In particular, after you've constructed the tree for s, go to the leaf representing the whole string and walk up until you see another end-of-string marker. This will be the leaf of the longest suffix that is also a prefix of s.

这篇关于算法的重复，但重复的字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！