1

我在这里做错了什么？

用于计算前缀函数的 Java 代码。两个输入是正确的，但最后一个是错误的。

这是伪代码：

伪代码

Java代码：

class Main {
// compute prefix function
    public static void main(String[] args) {
        String p = "422213422153342";
        String x = "ababbabbabbababbabb";
        String y = "ababaca";

        printOutput(p);

        printOutput(y);

        System.out.println();System.out.println();
        System.out.println("the prefix func below is wrong. I am not sure why.");
        System.out.print("answer should be: 0 0 1 2 0 1 2 0 1 2 0 1 2 3 4 5 6 7 8");

        printOutput(x);
    }

    static void printOutput(String P){
        System.out.println();System.out.println();
        System.out.print("p[i]: ");
        for(int i = 0; i < P.length(); i++)System.out.print(P.charAt(i) + " ");
        System.out.println();
        System.out.print("Pi[i]: ");
        compute_prefix_func(P);
    }
    public static void compute_prefix_func(String P){
        int m = P.length();
        int pi[] = new int[m];

        for(int i = 0; i < pi.length; i++){
            pi[i] = 0;
        }

        pi[0] = 0;

        int k = 0;

        for(int q = 2; q < m; q++){
            while(k > 0 && ( ((P.charAt(k) + "").equals(P.charAt(q) + "")) == false)){
                k = pi[k];
            }
            if ((P.charAt(k) + "").equals(P.charAt(q) + "")){
                k = k + 1;
            }
            pi[q] = k;
        }

        for(int i = 0; i < pi.length; i++){
        System.out.print(pi[i] + " ");
        }
    }
}
4

2 回答 2

5

好的，让我们从使代码更易于阅读开始。这：

if ((P.charAt(k) + "").equals(P.charAt(q) + ""))

可以简化为：

if (P.charAt(k) == P.charAt(q))

...而且您已经在多个地方做到了这一点。

同样在这里：

int pi[] = new int[m];

for(int i = 0; i < pi.length; i++){
    pi[i] = 0;
}

pi[0] = 0;

...您不需要显式初始化。默认情况下，变量初始化为 0。（目前还不清楚为什么要再次设置pi[0] ，尽管我注意到如果P.length()为 0，这将引发异常。）

接下来是删除与 的显式比较false，而不是仅使用!我们有：

while(k > 0 && P.charAt(k) != P.charAt(q))

最后，让我们稍微重构一下代码，使其更易于理解，使用更传统的名称，并改用int pi[]更惯用的名称int[] pi：

class Main {
    public static void main(String[] args) {
        String x = "ababbabbabbababbabb";

        int[] prefix = computePrefix(x);

        System.out.println("Prefix series for " + x);
        for (int p : prefix) {
            System.out.print(p + " ");
        }
        System.out.println();
    }

    public static int[] computePrefix(String input) {
        int[] pi = new int[input.length()];

        int k = 0;
        for(int q = 2; q < input.length(); q++) {            
            while (k > 0 && input.charAt(k) != input.charAt(q)) {
                k = pi[k];
            }
            if (input.charAt(k) == input.charAt(q)) {
                k = k + 1;
            }
            pi[q] = k;
        }
        return pi;
    }
}

现在更容易理解了，IMO。

我们现在可以回顾一下伪代码，发现它似乎对数组和字符串都使用了从 1 开始的索引。这让生活有点棘手。我们可以在整个代码中模仿这一点，将每个数组访问和charAt调用更改为仅减 1。

（我已经将公共子表达式提取到循环内的P[q]一个变量中。）target

public static int[] computePrefix(String input) {
    int[] pi = new int[input.length()];
    int k = 0;
    for (int q = 2; q <= input.length(); q++) {
        char target = input.charAt(q - 1);
        while (k > 0 && input.charAt(k + 1 - 1) != target) {
            k = pi[k - 1];
        }
        if (input.charAt(k + 1 - 1) == target) {
            k++;
        }
        pi[q - 1] = k;
    }
    return pi;
}

这现在给出了你想要的结果，但它真的很难看。我们可以q很容易地移动，并移除+ 1 - 1部件：

public static int[] computePrefix(String input) {
    int[] pi = new int[input.length()];
    int k = 0;
    for (int q = 1; q < input.length(); q++) {
        char target = input.charAt(q);
        while (k > 0 && input.charAt(k) != target) {
            k = pi[k - 1];
        }
        if (input.charAt(k) == target) {
            k++;
        }
        pi[q] = k;
    }
    return pi;
}

它仍然不完全令人愉快，但我认为这是你想要的。确保你明白为什么我必须做出我所做的改变。

于 2012-05-15T06:17:17.840 回答
0 
public static int[] computePrefix(String input) {
    int[] pi = new int[input.length()];
    pi[0] = -1;
    int k = -1;
    for (int q = 1; q < input.length(); q++) {
        char target = input.charAt(q);
        while (k > 0 && input.charAt(k + 1) != target) {
            k = pi[k];
        }
        if (input.charAt(k + 1) == target) {
            k++;
        }
        pi[q] = k;
    }
    return pi;
}
于 2017-11-05T03:18:45.947 回答