KMP Algorithm Notes

interview

Compute Prefix Table

The prefix table of a string $s$, $T[i]$ represents the length of the longest prefix of $s$ that is also the suffix of $s$ ends at index $i$ ($s[0...i]$)
Example :

i : 0 1 2 3 4 5 
s : a b a c a b
T : 0 0 1 0 1 2
________________________________
|  i |  j | s[i] | s[j] | T[i] |
--------------------------------
|  0 |  X |   a  |   X  |   0  |
--------------------------------
|  1 |  0 |   b  |   a  |   0  |  
|  2 |  0 |   a  |   a  |   1  |
|  3 |  1 |   c  |   b  |      |  j = T[j-1] = 0, search prefix from the beginning (of course!)
|  3 |  0 |   c  |   a  |   0  |
|  4 |  0 |   a  |   a  |   1  |
|  5 |  1 |   b  |   b  |   2  |
--------------------------------

public void computePrefixTable (int []T, String s){
    T[0] = 0;
    int i=1, j=0;
    int n = s.length();
    char []str = s.toCharArray();
    while(i<n){
        if(str[i]==str[j]){
            T[i] = j+1; // j is 0-based index, so j+1 is the length of prefix s[0..j]
            i++;
            j++;
        }else if(j>0){ // keep on search previously matched position
            j = T[j-1];
        }else{
            T[i] = 0; // re-match from the beginning
            i++;
        }
    }
}

Implement StrStr()

                        1 1 1 1 1
i : 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
s : a b c a b c d a b c d a b d e
p : a b c d a b d
j : 0 1 2 3 4 5 6
T : 0 0 0 0 1 2 0
___________________________
|  i |  j | s[i] | s[j] | 
---------------------------
|  0 |  0 |   a  |   a  |  
|  1 |  1 |   b  |   b  |
|  2 |  2 |   c  |   c  |
|  3 |  3 |   a  |   d  |  
--------------------------
                        1 1 1 1 1
i : 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
s : a b c a b c d a b c d a b d e
p :       a b c d a b d
j :       0 1 2 3 4 5 6
T :       0 0 0 0 1 2 0
__________________________
|  3 |  0 |   a  |   a  |   rematch p[0, m-1] from s[i-T[j-1],n-1], i fall back T[j-1]=0 steps 
|  4 |  1 |   b  |   b  |
|  5 |  2 |   c  |   c  |
|  6 |  3 |   d  |   d  |
|  7 |  4 |   a  |   a  |
|  8 |  5 |   b  |   b  |
|  9 |  6 |   c  |   d  | 
-------------------------
                        1 1 1 1 1
i : 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
s : a b c a b c d a b c d a b d e
p :               a b c d a b d
j :               0 1 2 3 4 5 6
T :               0 0 0 0 1 2 0
__________________________
|  7 |  0 |   a  |   a  |   rematch p[0, m-1] from s[i-T[j-1],n-1], i fall back T[6-1]=2 steps
|  8 |  1 |   b  |   b  | 
|  9 |  2 |   c  |   c  |
| 10 |  3 |   d  |   d  |
| 11 |  4 |   a  |   a  |
| 12 |  5 |   b  |   b  |
| 13 |  6 |   d  |   d  | 
-------------------------

// p is the pattern, s is the string used to search for p
// return start index in s if p is a substring of s, otherwise, -1
public int strStr(String s, String p){
    int n = s.length();
    int m = p.length();
    if(m==0) return 0;
    int [] T = new int[m];
    computePrefixTable(T, p);
    int i=0, j=0;
    while(i<n){
        if(s.charAt[i]== p.charAt(j)){
            if(j==m-1) return i-j;
            i++;
            j++;
        }else if(j>0){ //  i falls back T[j-1] steps, rematch from start index of p
            i= i- T[j-1];
            j= 0;
        }else{
            i++;
        }
    }
    return -1;
}