Knuth–Morris–Pratt Algorithm

KMP.java

public class KMP
{
    private final int R;       // the radix
    private int[][] dfa;       // the KMP automoton

    private char[] pattern;    // either the character array for the pattern
    private String pat;        // or the pattern string

    public KMP( String pat )
    {
        this.R = 256;
        this.pat = pat;

        int m = pat.length();
        dfa = new int[ R ][ m ]; 
        dfa[ pat.charAt( 0 ) ][ 0 ] = 1;

        for ( int x = 0, j = 1; j < m; j++ )
        {
            for ( int c = 0; c < R; c++ ) 
                dfa[ c ][ j ] = dfa[ c ][ x ];     // Copy mismatch cases. 
            dfa[ pat.charAt( j ) ][ j ] = j + 1;   // Set match case. 
            x = dfa[ pat.charAt( j ) ][ x ];     // Update restart state. 
        } 
    } 

    public KMP( char[] pattern, int R )
    {
        this.R = R;
        this.pattern = new char[ pattern.length ];

        for ( int j = 0; j < pattern.length; j++ )
            this.pattern[ j ] = pattern[ j ];

        int m = pattern.length;
        dfa = new int[ R ][ m ]; 
        dfa[ pattern[ 0 ] ][ 0 ] = 1;

        for ( int x = 0, j = 1; j < m; j++ )
        {
            for ( int c = 0; c < R; c++ ) 
                dfa[ c ][ j ] = dfa[ c ][ x ];     // Copy mismatch cases. 
            dfa[ pattern[ j ] ][ j ] = j + 1;      // Set match case. 
            x = dfa[ pattern[ j ] ][ x ];        // Update restart state. 
        } 
    } 

    public int search( String txt )
    {
        int m = pat.length();
        int n = txt.length();
        int i, j;

        for ( i = 0, j = 0; i < n && j < m; i++ )
        {
            j = dfa[ txt.charAt( i ) ][ j ];
        }

        if ( j == m ) return i - m;    // found
        return n;                    // not found
    }

    public int search( char[] text )
    {

        int m = pattern.length;
        int n = text.length;
        int i, j;

        for ( i = 0, j = 0; i < n && j < m; i++ )
        {
            j = dfa[ text[ i ] ][ j ];
        }

        if ( j == m ) return i - m;    // found
        return n;                    // not found
    }

    public static void main( String[] args )
    {
        String pat = args[ 0 ];
        String txt = args[ 1 ];
        char[] pattern = pat.toCharArray();
        char[] text    = txt.toCharArray();

        KMP kmp1 = new KMP( pat );
        int offset1 = kmp1.search( txt );

        KMP kmp2 = new KMP( pattern, 256 );
        int offset2 = kmp2.search( text );

        // print results
        StdOut.println( "text:    " + txt );

        StdOut.print( "pattern: " );

        for ( int i = 0; i < offset1; i++ )
            StdOut.print( " " );
        StdOut.println( pat );

        StdOut.print( "pattern: " );
        
        for ( int i = 0; i < offset2; i++ )
            StdOut.print( " " );
        StdOut.println( pat );
    }
}