|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcom.jaxfront.core.util.stringSearch.StringSearch
com.jaxfront.core.util.stringSearch.BNDM
public class BNDM
An implementation of the Backwards Non-deterministic Dawg (Directed
acyclic word graph) Matching algorithm by Gonzalo Navarro and
Mathieu Raffinot. See "A Bit-Parallel Approach to Suffix Automata: Fast
Extended String Matching" (appeared in Proceedings of the 9th Annual
Symposium on Combinatorial Pattern Matching, 1998).
This is one of the fastest algorithms, but it does not beat the
com.eaio.stringsearch.BoyerMooreHorspoolRaita
and the
com.eaio.stringsearch.BoyerMooreHorspool
algorithms.
Preprocessing: O(m) time Searching : O(n/m) (best case) O(n log|∑| m / m) (average) O(mn) (worst case)
Constructor Summary | |
---|---|
BNDM()
Constructor for BNDM. |
Method Summary | |
---|---|
java.lang.Object |
processBytes(byte[] pattern)
Pre-processing of the pattern. |
java.lang.Object |
processChars(char[] pattern)
Pre-processing of the pattern. |
int |
searchBytes(byte[] text,
int textStart,
int textEnd,
byte[] pattern,
java.lang.Object processed)
Returns the position in the text at which the pattern was found. |
int |
searchChars(char[] text,
int textStart,
int textEnd,
char[] pattern,
java.lang.Object processed)
Returns the index of the pattern in the text using the pre-processed Object. |
Methods inherited from class com.jaxfront.core.util.stringSearch.StringSearch |
---|
equals, getAllOccurences, hashCode, processString, searchBytes, searchBytes, searchBytes, searchBytes, searchBytes, searchChars, searchChars, searchChars, searchChars, searchChars, searchString, searchString, searchString, searchString, searchString, searchString, toString, toStringBuffer, usesNative, usesReflection |
Methods inherited from class java.lang.Object |
---|
getClass, notify, notifyAll, wait, wait, wait |
Constructor Detail |
---|
public BNDM()
Method Detail |
---|
public java.lang.Object processBytes(byte[] pattern)
int
array.
processBytes
in class StringSearch
pattern
- the byte
array containing the pattern, may not
be null
com.eaio.stringsearch.StringSearch#processBytes(byte[])
public java.lang.Object processChars(char[] pattern)
CharIntMap
.
processChars
in class StringSearch
pattern
- a char
array containing the pattern, may not be
null
com.eaio.stringsearch.StringSearch#processChars(char[])
public int searchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, java.lang.Object processed)
StringSearch
searchBytes
in class StringSearch
text
- text the byte
array containing the text, may
not be null
textStart
- at which position in the text the comparing should starttextEnd
- at which position in the text comparing should stoppattern
- the pattern to search for, may not be null
processed
- an Object as returned from StringSearch.processBytes(byte[])
, may
not be null
com.eaio.stringsearch.StringSearch#searchBytes(byte[], int, int,
byte[], java.lang.Object)
public int searchChars(char[] text, int textStart, int textEnd, char[] pattern, java.lang.Object processed)
StringSearch
searchChars
in class StringSearch
text
- the String containing the text, may not be null
textStart
- at which position in the text the comparing should starttextEnd
- at which position in the text comparing should stoppattern
- the pattern to search for, may not be null
processed
- an Object as returned from StringSearch.processChars(char[])
or
StringSearch.processString(String)
, may not be null
com.eaio.stringsearch.StringSearch#searchChars(char[], int, int,
char[], Object)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |