de.frame4j.text

Class KMP

java.lang.Object

de.frame4j.text.CleverSSS

de.frame4j.text.KMP

All Implemented Interfaces:

CharSequence, Comparable<CleverSSS>

@MinDoc(copyright="Copyright 2010  A. Weinert",
        author="Albrecht Weinert",
        version="V.33",
        lastModified="27.03.2021",
        usage="make for substrings to search for and use multiply",
        purpose="Knuth Morris Pratt substring search implementation")
public class KMP
extends CleverSSS

Subsequence search — the immutable state.

An object of this class represents a character sequence to be searched for in (longer) character sequences in all variants of "indexOf". A KMP object holds

• all immutable state
• plus some settings
• and methods
• implementing some search algorithms, in this class especially
  • Knuth Morris Pratt (KMP) — hence the class name KMP
  • and optimistic (O(n)) search guarded by a feasibility check.

The rationale behind Knuth Morris Pratt "indexOf" algorithms is that they very successfully strive for O(n). The standard ("naive" loop-in-loop) algorithms, also used in String and consorts, are of type O(n*m).

Knuth Morris Pratt does primarily compare character by character. But in the case of mismatches it has prepared a state machine (automaton) that tells where to go on with the search, thus avoiding to do any comparison twice (or even m times). This automaton is prepared once when making this KMP object.

The rationale behind making objects of this class immutable respectively restricting the state to the constant parts of a concrete KMP search is their multiple and threadsafe re-usability.

Motivation for clever subsequence searches and further background information see please in the abstract super class.


© Copyright 2009, 2010 Albrecht Weinert

Nested Class Summary

Nested classes/interfaces inherited from class de.frame4j.text.CleverSSS

CleverSSS.Simple

Field Summary

Fields

Modifier and Type	Field and Description
protected int[]	kmpSM The KPM automaton definition.

Fields inherited from class de.frame4j.text.CleverSSS

algName, ignoreCase, ignoreWS, len, mskMod, optimisticOK, primF, subC

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	KMP(char[] subC, int[] kmpSM, boolean ignoreCase, boolean ignoreWS, boolean optimisticOK) Constructor (for factory methods only, no checks).
protected	KMP(char subOne, boolean ignoreCase, boolean ignoreWS) Constructor (for factory methods only, no checks), one character only case.

Method Summary

Modifier and Type	Method and Description
protected long	implAlgWhere(CharSequence sequ, int lk, int sI, int mxSi) The basic implementation of the KMP search algorithm using this object's settings.
protected int	implAlgWhere(long[] therFnd, CharSequence sequ, int lk, int sI, int mxSi, boolean overlap) The algorithmic implementation of allWhere().
static CleverSSS	make(CharSequence sub, boolean ignoreCase) Make a KMP for a subsequence to be searched for.
static CleverSSS	make(CharSequence sub, boolean ignoreCase, boolean ignoreWS) Make a KMP for a subsequence to be searched for (later).
String	state() The state as String.

Methods inherited from class de.frame4j.text.CleverSSS

allWhere, asPair, asPairs, charAt, commonState, compareTo, endIndexOf, endIndexOf, equals, hashCode, indexOf, indexOf, lastIndexOf, lastIndexOf, lastWhereImpl, length, make, make, makeSimple, pair2long, subSequence, toCharA, toString, where, where, whereImpl

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.CharSequence

chars, codePoints

Field Detail

kmpSM

protected final int[] kmpSM

The KPM automaton definition.

Constructor Detail

KMP

protected KMP(char[] subC,
              int[] kmpSM,
              boolean ignoreCase,
              boolean ignoreWS,
              boolean optimisticOK)

Constructor (for factory methods only, no checks).

KMP

protected KMP(char subOne,
              boolean ignoreCase,
              boolean ignoreWS)

Constructor (for factory methods only, no checks), one character only case.

Method Detail

make

public static CleverSSS make(CharSequence sub,
                             boolean ignoreCase)

Make a KMP for a subsequence to be searched for.

This method makes and returns a KMP object for the sub sequence supplied. That object is suitable for subsequent multiple and multi-thread searches for that sub sequence. If (all) that searches are to ignore case, this has to be (finally) set here.

make

public static CleverSSS make(CharSequence sub,
                             boolean ignoreCase,
                             boolean ignoreWS)

Make a KMP for a subsequence to be searched for (later).

This method is equivalent to make(CharSequence, boolean) with the extra option to make the subsequence search totally white space ignoring if the the third parameter ignoreWS is supplied as true.

In that case only sub's non blank characters would be transferred to the KMP object to be made.

Example: A search for "al L" in " H a l l o " both ignoring white space and case would yield 3 as the first matching index (and 8 as the first non matching index after the fitting sub sequence pattern).

state

public String state()

Description copied from class: CleverSSS

The state as String.

This method returns information about the immutable state of this CleverSSS object. The purpose is debugging or fabrication of often used searches. The result is usually multi line.

Overrides:

state in class CleverSSS

implAlgWhere

protected final long implAlgWhere(CharSequence sequ,
                                  int lk,
                                  int sI,
                                  int mxSi)

The basic implementation of the KMP search algorithm using this object's settings.

This method is called by CleverSSS.whereImpl(CharSequence, int, int) for all non trivial cases and with checked / correct parameters.

Specified by:

implAlgWhere in class CleverSSS

Parameters:

sequ - the sequence to search in

lk - its correct or shortened) length

sI - the starting index for the search

mxSi - the maximum possible value of the match index

Returns:

first index and last index + 1 where sub was found in one long or -1 if no match

See Also:

CleverSSS.implAlgWhere()

implAlgWhere

protected int implAlgWhere(long[] therFnd,
                           CharSequence sequ,
                           int lk,
                           int sI,
                           int mxSi,
                           boolean overlap)

The algorithmic implementation of allWhere().

Called by allWhere() after handling all trivial, exceptional, illegal and optimistic cases.

This implementation exploits the fact that the KPM algorithm is predestined for consecutive multiple searches.

Overrides:

implAlgWhere in class CleverSSS