如何使用/修改Knuth-Morris-Pratt算法将任意给定的字符串转换为回文字符串

Question

我被分配了一个任务，要创建一个类，给定一个字符串，用最少的断言创建一个回文。

示例运行：

Input: 123333
Output: 12333321

Input: 789
Output: 78987

Input: 1221
Output: 1221221

注意回文不应该返回相同的回文。

我尝试使用修改过的KMP算法，如这里所述。

我将字符串反转并与反向+原始字符串进行比较，然后将不匹配项添加到原始字符串中。

然而，我的函数仅适用于具有尾随数字的输入（第一个示例输入），但类似于1234的输入将返回1234123，'92837465'将返回'928374659283746'

public static int[] computelps(String sample){
    int[] lps = new int[sample.length()];
    lps[0] = 0;
    int i = 1;
    int len = 0; // length of previous longest prefix suffix
    while (i < sample.length()) {
        if (sample.charAt(i) == sample.charAt(len)) {
            len++;
            lps[i] = len;
            i++;
        }
        else
        {
            if (len != 0) {
                len = lps[len - 1];
            }
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

public static void Solution(File samplefile) throws Exception {
    BufferedReader br = new BufferedReader(new FileReader(samplefile));

    String firstline = br.readLine();
    String line;


    while ((line = br.readLine()) != null) {
        String reverse_str = "";
        String newline = line.replace(".", "");

        for (int i = newline.length() - 1; i >= 0; i--) {
            reverse_str += newline.charAt(i);
        }

        int [] lps = computelps(reverse_str); // computes the lps of the pattern string
        String tot = reverse_str + newline;

        // KMP Algorithm modified.

        int x = 0; // index for total_string(tot)
        int y = 0; // index for pattern
        String palindrome = newline;

        while (x < tot.length()){
            if(reverse_str.charAt(y) == tot.charAt(x)){
                y++;
                x++;
            }
            if(y == reverse_str.length()) {
                y = lps[y - 1];
            }


            else if( x < tot.length() && (reverse_str.charAt(y) != tot.charAt(x))){
                palindrome += tot.charAt(x);
                if ( y!= 0){
                    y = lps[y-1];
                }
                else{
                    x += 1;
                }
            }
        }
        System.out.println(palindrome);
    }
}

我很感激您的帮助。我认为算法非常具有挑战性，如果我的方法或代码不太好，请多多包容。

*我更正了样本输入和输出，并添加了我的结果。

- Reemz

---

你确定你列出的输入和预期输出是正确的吗？例如，为什么输入1221应该得到12211221的输出？难道不应该是1221221吗？因为这是创建回文所需的最少添加次数。 - Jordan

computelps("4321")应该返回什么？ - GabiM

computelps("4321.") 将返回 [ 0, 0, 0, 0 ]。 - Reemz

Answer 1

将问题分解为较小的问题，为每个问题实现一个单独的方法，并检查每个方法是否按预期工作，这有助于解决问题。学会在您的IDE中使用调试器将真正帮助您。但在此之前，您可以测试代码的每个部分是否按预期工作。因此，我简化了您的代码并将其拆分为以下几个部分：

public static void main(String[] args){
        System.out.println("computelps " + ("[0, 0, 0, 0]".equals(Arrays.toString(computelps("4321"))) ? "works" : "doesn't work" ));   
        System.out.println("reverse " + ("4321".equals(reverse("1234")) ? "works" : "doesn't work" ));
        System.out.println("Solution " + ("1234321".equals(Solution("1234")) ? "works" : "doesn't work" ));
    }

    public static int[] computelps(String sample){
        int[] lps = new int[sample.length()];
        lps[0] = 0;
        int i = 1;
        int len = 0; // length of previous longest prefix suffix
        while (i < sample.length()) {
            if (sample.charAt(i) == sample.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            }
            else
            {
                if (len != 0) {
                    len = lps[len - 1];
                }
                else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static String Solution(String line) {
        String newline = line.replace(".", "");
        String reverse_str = reverse(newline);

        int [] lps = computelps(reverse_str); // computes the lps of the pattern string

        // KMP Algorithm modified.

        return kpmModified(newline, reverse_str, lps);

    }

    private static String kpmModified(String newline, String reverse_str, int[] lps) {
        int x = 0; // index for total_string(tot)
        int y = 0; // index for pattern
        String tot = reverse_str + newline;
        String palindrome = newline;

        while (x < tot.length()){
            if(reverse_str.charAt(y) == tot.charAt(x)){
                y++;
                x++;
            }
            if(y == reverse_str.length()) {
                y = lps[y - 1];
            }


            else if( x < tot.length() && (reverse_str.charAt(y) != tot.charAt(x))){
                palindrome += tot.charAt(x);
                if ( y!= 0){
                    y = lps[y-1];
                }
                else{
                    x += 1;
                }
            }
        }
        return palindrome;
    }

    private static String reverse(String newline) {
        String reverse_str = "";

        for (int i = newline.length() - 1; i >= 0; i--) {
            reverse_str += newline.charAt(i);
        }
        return reverse_str;
    }

结果是

computelps works
reverse works
Solution doesn't work

所以你的bug在kpmModified方法中。我不能再花更多时间了，而且我对算法不太熟悉，但你应该继续下去，找出那个方法中有问题的部分。

- GabiM

Answer 2

我认为你过于复杂化了这个问题。问题基本上是将一个字符串的反转版本添加回原始字符串，但不是每个字符都需要添加，对吧？因此，您可能需要找到类似指针的东西，告诉函数从哪里开始反转。

举个例子，让字符串为12333。如果我们从索引string.length()到0添加每个字符，它将变成1233333321，这是不正确的，因为有重复的3。我们需要忽略那些，所以我们需要从string.length() - numOfDuplicateAtEnd到0添加字符。

    public String palindromic(String num) {
        int i = num.length() - 1;
        while (i > -1 && num.charAt(i) == num.charAt(num.length() - 1))  
            i--;

        for (int k = i; k > -1; --k) 
            num += num.substring(k, k + 1);

        return num;
    }

- Will

---

请尝试通过提供一些代码来使您的答案更完整。 - francoisr