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

Question

我的任务是创建一个给定字符串的类，该类将创建一个断言数量最少的回文。

示例运行:

Input: 123333
Output: 12333321

Input: 789
Output: 78987

Input: 1221
Output: 1221221

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

我尝试使用改进的 KMP 算法，如 here 所述.

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

然而，我的函数仅适用于带有尾随数字的输入(第一个示例输入)，但是像 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);
    }
}

如果有任何帮助，我将不胜感激。我发现算法非常具有挑战性，所以如果我的方法或代码低于标准，请多多包涵。

*我修复了示例输入和输出并添加了我的结果。

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

所以你的错误在 kpmModified 方法中。我不能花更多的时间而且我不熟悉该算法，但你应该继续这样并找出我们该方法的哪一部分有错误。