KMP Skip Table not producing the correct output

21 Views Asked by At

I can't figure out where I am going wrong, could someone please advise as you can see my output is really close to what I want but I can't figure out what checks/conditions I am missing

`public class KMPtable {
    public static void main(String[] args) {
        String pattern = "xyxyz";
        printPattern(pattern);
        generateSkipTable(pattern);
    }

    private static void printPattern(String pattern) {
        System.out.print("    ");
        for (int i = 0; i < pattern.length(); i++) {
            System.out.print(pattern.charAt(i) + "  ");
        }
        System.out.println();
    }

    private static void generateSkipTable(String pattern) {
        for (int i = 0; i < pattern.length(); i++) {
            char currentChar = pattern.charAt(i);
            // Only want to start initializing skip table generation
            // when we hit a unique char
            if (i == pattern.indexOf(currentChar)) {
                System.out.print(currentChar + "   ");
                for (int j = 0; j < pattern.length(); j++) {
                    int lastCharIndex = pattern.lastIndexOf(currentChar, j);
                    int prefix = j;
                    int suffix = pattern.length() - j;
                    int skipVal = 0;

                    // Character is not found in the pattern where we are at
                    if (lastCharIndex == -1) {
                        skipVal = j + 1;
                    } else {
                        if (currentChar == pattern.charAt(j)) {
                            skipVal = 0;
                        } else { // char does not match
                            if (prefix < suffix) {
                                skipVal = lastCharIndex + 1;
                            } else {
                                skipVal = j;

                            }
                        }
                    }

                    System.out.print(String.format("%-2d ", skipVal));
                }
                System.out.println();
            }
        }

        // Wildcard case where char does not match any char in the pattern
        System.out.print("*   ");
        for (int i = 0; i < pattern.length(); i++) {
            System.out.print((i + 1) + "  ");
        }
    }
} `

And this is the output:

    x  y  x  y  z  
x   0  1  0  3  4  
y   1  0  2  0  4  
z   1  2  3  4  0  
*   1  2  3  4  5  

This is the expected output:

    x y x y z
x   0 1 0 3 2
y   1 0 3 0 5
z   1 2 3 4 0
*   1 2 3 4 5

I don't understand why the values are not being calculated correctly in some cases

0

There are 0 best solutions below