Compute Prefix Function in String Matching

Question

What am i doing wrong here?

Java code for computing prefix function. Two input are right but the last one is wrong.

Here's the pseudocode:

Java code:

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

Okay, let's start off by making the code much easier to read. This:

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

can be simplified to:

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

... and you've done that in multiple places.

Likewise here:

int pi[] = new int[m];

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

pi[0] = 0;

... you don't need the explicit initialization. Variables are 0-initialized by default. (It's unclear why you're then setting pi[0] again, although I note that if P.length() is 0, this will throw an exception.)

Next is to remove the explicit comparison with false, instead just using ! so we have:

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

Finally, let's restructure the code a bit to make it easier to follow, use more conventional names, and change int pi[] to the more idiomatic 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;
    }
}

That's now much easier to follow, IMO.

We can now look back to the pseudocode and see that it appears to be using 1-based indexing for both arrays and strings. That makes life slightly tricky. We could mimic that throughout the code, changing every array access and charAt call to just subtract 1.

(I've extracted the common subexpression of P[q] to a variable target within the loop.)

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

That now gives your desired results, but it's really ugly. We can shift q very easily, and remove the + 1 - 1 parts:

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

It's still not entirely pleasant, but I think it's what you want. Make sure you understand why I had to make the changes I did.