17

我需要编写一个方法，给我一个字符串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));
    }
}

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

4

6 回答 6

9

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

于 2012-07-15T08:42:09.247 回答
3

正如@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);
}
于 2012-07-15T12:07:12.867 回答
2

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

于 2012-07-15T07:48:38.650 回答
2

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

于 2012-07-15T12:37:43.717 回答
0

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

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

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

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"
于 2012-07-15T09:02:37.273 回答
-1

据我了解，您想这样做：

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

希望这有帮助！

于 2012-07-15T07:54:22.663 回答