KMP

Last Updated: 2021-12-15

import java.io.IOException;

public class Test {

    public static void main(String[] args) throws IOException {
        System.out.println(kmp("ABC ABCDAB ABCDABCDABDE", "ABCDABD"));
    }

    public static int kmp(String text, String pattern) {
        char[] t = text.toCharArray();
        char[] p = pattern.toCharArray();
        int[] table = getTable(p);
        int i = 0, j = 0;
        while (i < t.length && j < p.length) {
            if (t[i + j] == p[j]) {
                if (j == p.length - 1) return i;
                j++;
            } else if (table[j] > -1) {
                i = i + j - table[j];
                j = table[j];
            } else {
                i++;
                j = 0;
            }
        }
        return -1;
    }

    private static int[] getTable(char[] pattern) {
        int[] table = new int[pattern.length];
        table[0] = -1;
        table[1] = 0;
        int i = 2, j = 0;
        while (i < pattern.length) {
            if (pattern[i - 1] == pattern[j]) {
                table[i] = j + 1;
                i++;
                j++;
            } else if (j > 0) {
                j = table[j];
            } else {
                table[i] = 0;
                i++;
            }
        }
        return table;
    }
}