Package dsa

Class KMP

java.lang.Object
dsa.KMP
public class KMP extends Object
A data type to find the first occurrence of a pattern string within a text string, using the Knuth-Morris-Pratt (KMP) substring search algorithm.

  • Constructor Summary

    Constructors
    Constructor
    Description
    KMP(String pattern, int radix)
    Preprocesses the pattern string with alphabet size given by radix.

  • Method Summary

    Modifier and Type
    Method
    Description
    static void
    main(String[] args)
    Unit tests the data type.
    int
    search(String text)
    Returns the index of the first occurrence of the pattern string within the text string, or the length of the text string.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • KMP

      public KMP(String pattern, int radix)
      Preprocesses the pattern string with alphabet size given by radix.
      Parameters:
      pattern - the pattern string.
      radix - the alphabet size.

  • Method Details

    • search

      public int search(String text)
      Returns the index of the first occurrence of the pattern string within the text string, or the length of the text string.
      Parameters:
      text - the text string.
      Returns:
      the index of the first occurrence of the pattern string within the text string, or the length of the text string.

    • main

      public static void main(String[] args)
      Unit tests the data type.
      Parameters:
      args - the command-line arguments.