在字符串匹配中计算前缀函数

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]到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;
}

它仍然不是很愉快,但我认为这是你想要的.确保你理解为什么我必须做出我所做的改变.