String Matching Techniques: KMP Algorithm

Code (GeeksForGeeks):

import java.util.Arrays;

class KMPAlgo {
static public int[] getLPS(char[] pattern) {
int m = pattern.length;
int[] lps = new int[m];

int i = 1;
lps[0] = 0;

int len = 0;

while(i < m) {
if(pattern[i] == pattern[len]) {
len++;
lps[i] = len;
++i;
} else {
if(len == 0) {
lps[i] = 0;

++i;
} else
len = lps[len-1];
}
}

return lps;
}

static public void searchForPattern(char[] pattern, char[] text, int[] lps) {
int m = pattern.length, n = text.length;

int i = 0, j = 0;

while(i < n) {
if(pattern[j] == text[i]) {
++i;
++j;
}

if(j == m) {
System.out.println("Pattern found at: " + (i-j));

j = lps[j-1];
}

if(i<n && pattern[j] != text[i]) {
if(j != 0)
j = lps[j-1];
else
++i;
}
}
}

static public void main(String[] args) {
String pattern = "ABABCABAB", text = "ABABDABACDABABCABAB";

int[] lps = getLPS(pattern.toCharArray());

System.out.println(pattern);
System.out.println(text);
System.out.println(Arrays.toString(lps));

searchForPattern(pattern.toCharArray(), text.toCharArray(), lps);
}
}

---------------------------------------------------------






In this algorithm, we first build a Fail/Prefix function with the given pattern to be matched.

Algorithm to build the Fail function:
1. Initialize the initial indices of i and j as: i = 0, j = 1
2. Define the fail function integer array and initialize the the first two elements as -1 and 0.
F[0] = -1 and F[1] = 0
3. Now compare the two characters at indices i and j of Pattern P. Two cases are possible
Case 1: P[i] == P[j]
==>Then, increment fail function value by 1 of previous value, i.e. F[j+1] = F[j] + 1
       and increment both i and j by 1
Case 2: P[i] != P[j]
==> Now reinitialize the value of i to 0 and compare the elements again
        Case 2 i: P[i] == P[j]
        ==> Keep the fail function value as previous one, i.e. F[j+1] = F[j]
                increment both i and j by 1
        Case 2 ii: P[i] != P[j]
        ==> Keep the fail function value as zero, i.e. F[j+1] = 0
                increment only j value.

Observations:
If characters are equal, then we increment both i and j, if not equal, then we increment only j
j value is always incremented

(Source: https://www.youtube.com/watch?v=1k2KDhcO_uo)

Java Program to build the Fail function:

import java.util.Arrays;

class KMPAlgo {
        static public int[] getFailFunction(String pattern) {
                int i = 0, j = 1;
                int[] failFunc = new int[pattern.length()];

                char[] P = pattern.toCharArray();

                failFunc[0] = -1;
                failFunc[1] = 0;

                while(j<pattern.length()-1) {
                        if(P[i] == P[j]) {
                                //increment element by 1
                                failFunc[j+1] = failFunc[j] + 1;
                                ++i;
                                ++j;
                        } else {
                                //make i to 0 and do the comparision again
                                i = 0;

                                if(P[i] == P[j]) {
                                        failFunc[j+1] = failFunc[j];
                                        ++i;
                                        ++j;
                                } else {
                                        failFunc[j+1] = 0;
                                        ++j;
                                }
                        }
                }

                return failFunc;
        }

        static public void main(String[] args) {
                String pattern = "abaababaabc";
                //pattern = "abcabdaab";

                int[] failFunc = getFailFunction(pattern);

                System.out.println(Arrays.toString(failFunc));
        }
}

eg:
Pattern: abaababaabc

> i=0, j=1, F[0] = -1, F[1] = 0
Compare P[i] and P[j]: P[0] and P[1], a != b
So falls into Case 2 and since i is already 0, so we keep F[j+1] = F[1+1] = F[2] = 0
and increment j by 1

> i=0, j=2, F[2] = 0
Compare P[i] and P[j]: P[0] and P[2], a == a
So falls into Case 1, so increment fail function value: F[j+1] = F[2+1] = F[3] = 1
and increment both i and j

> i=1, j=3, F[3] = 1
Compare P[i] and P[j]: P[1] and P[3]: b != a
So falls into Case 2. reinitialize i to 0 and Compare P[i] with P[j]
P[0] and P[3]: a == a
So keep fail function value same as previous: F[j+1] = F[j]: F[4] = F[3] = 1
and increment both i and j

> i=2, j=4, F[4] = 1

...