Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Knuth–Morris–Pratt Algorithm
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 );
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment