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

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

我知道我的问题很可能在算法层面上有误，而不是在编码层面上。请问我的算法应该怎么样？

- OneMoreError

---

+1 是因为我不理解为什么有人要给这个问题投反对票，这个问题在我看来似乎是非常合理的。 - John

这看起来非常像家庭作业。@CSSS，这是家庭作业吗？ - Esko

@CSSS：这看起来很像作业。如果是的话，你应该在问题中添加[标签：作业]标签。 - Darshan Rivka Whittle

@Esko和Fahim：不，这不是作业。我只是为了好玩而尝试它们。 - OneMoreError

@CSSS 请查看我的代码编辑，我刚刚发布的代码应该是你要找的。 - John

Answer 1

使用后缀树。特别是，在为s构建树之后，转到代表整个字符串的叶子节点，并向上移动，直到看到另一个字符串结尾标记。这将是最长后缀同时也是s的前缀的叶子节点。

- phs

Answer 2

正如@phs所说，问题的一部分可以翻译为"找到字符串s的最长前缀，该前缀也是s的后缀"。一种不需要树的解决方案可能是：

public static String getShortest(String s) {
    int i = s.length();
    while(i > 0 && !s.endsWith(s.substring(0, --i))) 
        ;
    return s + s.substring(i);
}

- Arne

Answer 3

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

- JB Nizet

Answer 4

我认为你应该看一下Knuth-Morris-Pratt算法，它使用的部分匹配表几乎就是你需要的（顺便说一句，这是一个非常好的算法 ;)）。

- Zoltán Haindrich

Answer 5

如果您的输入字符串s是，比如"abcde"，您可以轻松地构建像以下这样的正则表达式（注意最后一个字符"e"被省略了！）：

a(b(c(d)?)?)?$

并在字符串s上运行它。这将返回尾部重复子字符串的起始位置。然后，您只需附加缺失的部分（即s的最后N-M个字符，其中N是s的长度，M是匹配的长度），例如：

aba
  ^ match "a"; append the missing "ba"
xxxxxx
 ^ match "xxxxx"; append the missing "x"
abracadabra
       ^ match "abra"; append the missing "cadabra"
nooverlap
--> no match; append "nooverlap"

- CAFxX

Answer 6

根据我的理解，您想要做到这一点：

input: dog
output: dogdog
--------------
input: racecar
output: racecaracecar

这是我会这样做的：

 public String change(String input)
{
    StringBuilder outputBuilder = new StringBuilder(input);

    int patternLocation = input.length();
    for(int x = 1;x < input.length();x++)
    {
        StringBuilder check = new StringBuilder(input);

        for(int y = 0; y < x;y++)
            check.deleteCharAt(check.length() - 1);

        if(input.endsWith(check.toString()))
        {
            patternLocation = x;
            break;
        }
    }

    outputBuilder.delete(0,  input.length() - patternLocation);

    return outputBuilder.toString();
}

希望这有所帮助！

- John

---

@JBNizet 这个问题为什么不满足要求呢？ - John

abracadabra 应该变成 abracadabracadabra，而不是 abracadabrabracadabra。问题已经很清楚了，你只需要关注第一个和最后一个字符。这不是问题所要求的。 - JB Nizet

@Lion 嗯，我不知道 StringBuilder 是 StringBuffer 的“替代品”，我想从现在开始我会使用它。 - John

@JBNizet 噢，好的，我明白你的意思了，我没有注意到那个。 - John

如果你说它能工作，我会相信你。但我无法理解这个算法。原帖中的算法要简单得多，而且不需要两个循环。虽然如此，我会取消我的踩票。 - JB Nizet