private void computeMatch() {
    /* Phase 1 */
        for (int j = 0; j < match.length; j++) {
            match[j] = match.length;
        } //O(m)

        computeSuffix(); //O(m)

    /* Phase 2 */
        //Uses an auxiliary array, backwards version of the KMP failure function.
        //suffix[i] = the smallest j > i s.t. p[j..m-1] is a prefix of p[i..m-1],
        //if there is no such j, suffix[i] = m

        //Compute the smallest shift s, such that 0 < s <= j and
        //p[j-s]!=p[j] and p[j-s+1..m-s-1] is suffix of p[j+1..m-1] or j == m-1},
        //                                                         if such s exists,
        for (int i = 0; i < match.length - 1; i++) {
            int j = suffix[i + 1] - 1; // suffix[i+1] <= suffix[i] + 1
            if (suffix[i] > j) { // therefore pattern[i] != pattern[j]
                match[j] = j - i;
            } else {// j == suffix[i]
                match[j] = Math.min(j - i + match[i], match[j]);
            }
        } //End of Phase 2

    /* Phase 3 */
        //Uses the suffix array to compute each shift s such that
        //p[0..m-s-1] is a suffix of p[j+1..m-1] with j < s < m
        //and stores the minimum of this shift and the previously computed one.
        if (suffix[0] < pattern.length()) {
            for (int j = suffix[0] - 1; j >= 0; j--) {
                if (suffix[0] < match[j]) { match[j] = suffix[0]; }
            }
            int j = suffix[0];
            for (int k = suffix[j]; k < pattern.length(); k = suffix[k]) {
                while (j < k) {
                    if (match[j] > k) match[j] = k;
                    j++;
                }
            }
        }//endif
    }
private void computeMatch ( ) { for ( int j = 0 ; j < match . length ; j ++ ) { match [ j ] = match . length ; } computeSuffix ( ) ; for ( int i = 0 ; i < match . length - 1 ; i ++ ) { int j = suffix [ i + 1 ] - 1 ; if ( suffix [ i ] > j ) { match [ j ] = j - i ; } else { match [ j ] = Math . min ( j - i + match [ i ] , match [ j ] ) ; } } if ( suffix [ 0 ] < pattern . length ( ) ) { for ( int j = suffix [ 0 ] - 1 ; j >= 0 ; j -- ) { if ( suffix [ 0 ] < match [ j ] ) { match [ j ] = suffix [ 0 ] ; } } int j = suffix [ 0 ] ; for ( int k = suffix [ j ] ; k < pattern . length ( ) ; k = suffix [ k ] ) { while ( j < k ) { if ( match [ j ] > k ) match [ j ] = k ; j ++ ; } } } }
Computes the function <i>match</i> and stores its values in the array <code>match</code>.
The function is defined as follows:
<pre>
match(j) = min{ s | 0 < s <= j && p[j-s]!=p[j]
&& p[j-s+1]..p[m-s-1] is suffix of p[j+1]..p[m-1] },
if such s exists, else
min{ s | j+1 <= s <= m
&& p[0]..p[m-s-1] is suffix of p[j+1]..p[m-1] },
if such s exists,
m, otherwise,
where m is the pattern's length and p is the pattern.
</pre>
The running time is O(pattern.length()).