Class KMPMatching

java.lang.Object
io.github.connellite.match.KMPMatching

public class KMPMatching extends Object
Knuth–Morris–Pratt (KMP) substring search for CharSequence and byte arrays.

Time complexity is O(n + m) for text length n and pattern length m.

  • Constructor Details

    • KMPMatching

      public KMPMatching()
  • Method Details

    • isMatch

      public static boolean isMatch(CharSequence text, CharSequence pattern)
      Independent KMP implementation.
      Parameters:
      text - source text; not null
      pattern - searched substring; not null
      Returns:
      true if text contains pattern
    • performKMPSearch

      public static List<Integer> performKMPSearch(CharSequence text, CharSequence pattern)
      Finds all starting indices of pattern in text.
      Parameters:
      text - text to search; not null
      pattern - substring to find; not null (empty pattern yields an empty result)
      Returns:
      mutable list of zero-based start indices, in ascending order
    • indexOfByteArray

      public static int indexOfByteArray(byte[] data, byte[] pattern)
      Returns the zero-based index of the first occurrence of pattern in data, or -1 if not found.
      Parameters:
      data - bytes to search; not null
      pattern - byte sequence to find; not null
      Returns:
      start index of first match, or -1 if data or pattern is empty or no match exists