Package io.github.connellite.match
Class KMPMatching
java.lang.Object
io.github.connellite.match.KMPMatching
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 Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic intindexOfByteArray(byte[] data, byte[] pattern) Returns the zero-based index of the first occurrence ofpatternindata, or-1if not found.static booleanisMatch(CharSequence text, CharSequence pattern) Independent KMP implementation.performKMPSearch(CharSequence text, CharSequence pattern) Finds all starting indices ofpatternintext.
-
Constructor Details
-
KMPMatching
public KMPMatching()
-
-
Method Details
-
isMatch
Independent KMP implementation.- Parameters:
text- source text; not nullpattern- searched substring; not null- Returns:
trueiftextcontainspattern
-
performKMPSearch
Finds all starting indices ofpatternintext.- Parameters:
text- text to search; not nullpattern- 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 ofpatternindata, or-1if not found.- Parameters:
data- bytes to search; not nullpattern- byte sequence to find; not null- Returns:
- start index of first match, or
-1ifdataorpatternis empty or no match exists
-