Class KMP

java.lang.Object

KMP

public class KMP
extends java.lang.Object

This class implements the Knuth-Morris-Pratt algorithm to search for an occurrence of a given string pat in a given string txt. (The first string is called pattern, the second is called text.) The KMP algorithm simulates a deterministic finite-state automaton (DFA).

An example of output of the teste client:

  % java KMP abracadabra abacadabrabracabracadabrabrabracad
  text:    abacadabrabracabracadabrabrabracad 
  pattern:               abracadabra          
  

Constructor Summary

Constructors

Constructor and Description
KMP(char[] pattern, int R) Creates the DFA from a pattern over an R-character alphabet.
KMP(java.lang.String pat) Creates the DFA for a pattern over the extended ASCII alphabet.

Method Summary

Methods

Modifier and Type	Method and Description
static void	main(java.lang.String[] args) Test client.
int	search(char[] text) Returns offset of first match of pattern in text; returns N if no match The text is a character array.
int	search(java.lang.String txt) Returns offset of first match of pattern in text; returns N if no match.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

KMP

public KMP(java.lang.String pat)

Creates the DFA for a pattern over the extended ASCII alphabet. Treats pattern as a string.

KMP

public KMP(char[] pattern,
   int R)

Creates the DFA from a pattern over an R-character alphabet. Treats pattern as a character array.

Method Detail

search

public int search(java.lang.String txt)

Returns offset of first match of pattern in text; returns N if no match. The text is a String.

search

public int search(char[] text)

Returns offset of first match of pattern in text; returns N if no match The text is a character array.

main

public static void main(java.lang.String[] args)

Test client. Examples of output:

  % java KMP abracadabra abacadabrabracabracadabrabrabracad
  text:    abacadabrabracabracadabrabrabracad 
  pattern:               abracadabra          

  % java KMP rab abacadabrabracabracadabrabrabracad
  text:    abacadabrabracabracadabrabrabracad 
  pattern:         rab

  % java KMP bcara abacadabrabracabracadabrabrabracad
  text:    abacadabrabracabracadabrabrabracad 
  pattern:                                   bcara

  % java KMP rabrabracad abacadabrabracabracadabrabrabracad 
  text:    abacadabrabracabracadabrabrabracad
  pattern:                        rabrabracad

  % java KMP abacad abacadabrabracabracadabrabrabracad
  text:    abacadabrabracabracadabrabrabracad
  pattern: abacad