java - 字符串匹配中的计算前缀函数

Question

我做错了什么？

计算前缀函数的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] + " ");
        }
    }
}

Answer 1

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

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] 的公共(public)子表达式提取到循环中的变量 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;
}

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