Knuth-Morris-Pratt algorithm (KMP)

Haii gan kali ini ane bahas tentang knuth-morrs-prat algoritma oke langsung aja gan tanpa basa-basi lagi langsung ke TKP..!!! 

Algoritma KMP merupakan proses awal (preprocessing) terhadap pattern dengan menghitung fungsi pinggiran. Pada beberapa literatur disebut fungsi overlap,fungsi failure,fungsi awalan, dan sebagainya.Fungsi ini mengindikasikan pergeseran terbesar yang mungkin dengan menggunakan perbandingan yang dibentuk sebelum pencarian string.

Contoh:

public static int occurrenceOfSubstring(char[] target, char[] pattern) {
        int[] overlay = new int[pattern.length];
        overlay[0] = -1;
        overlay[1] = 0;

        int i = 0, j = 1;

        while (j + 1 < pattern.length) {
            if (pattern[i] == pattern[j]) {
                if (i == 0) {
                    overlay[j + 1] = 1;
                } else {
                    overlay[j + 1] = overlay[j] + 1;
                }
                i++;
                j++;
            } else if (pattern[j] == pattern[0]) {
                i = 0;
            } else {
                j++;
            }
        }

        int l = 0,count=0;

        for (int k = 0; k < target.length; k++) {
            if (target[k] == pattern[l]) {
                if (l == pattern.length - 1) {
                    l = 0;
                    count++;
                } else {
                    l++;
                }
            } else {
                l = overlay[l] == -1 ? 0 : overlay[l];
            }
        }
        return count;
    }

Oke gan mungkin itu dulu semoga bermanfaat..!!!