|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.biojava.bio.search.KnuthMorrisPrattSearch
An object to find exact subsequences within a sequence.
Reference: KNUTH D.E., MORRIS (Jr) J.H., PRATT V.R., 1977, Fast pattern matching in strings, SIAM Journal on Computing 6(1):323-350. USAGE:
When the object is constructed thefindMatches()
method would be called. This will return an int[] giving the offsets
(ie the location of the first symbol of each match in the text).
The getKMPNextTable()
returns the table of border lengths
used in the algorithm. This method is protected as it is unlikely it
will be needed except for debugging.
The algorithm finds exact matches therefore ambiguity symbols will match only themselves. The class cannot perform regular expressions. The class operates on all alphabets thus if searching for a DNA pattern you should compile both the pattern and its reverse complement.
WARNING the behaviour of a pattern containing gaps is undefined. It's not recommended that you try it.
Copyright: Copyright (c) 2002
Company: AgResearch
Constructor Summary | |
KnuthMorrisPrattSearch(SymbolList pattern)
Constructs a KMP matcher to find exact occurances of pattern in text using the
Knuth-Morris-Pratt algorithm. |
Method Summary | |
int[] |
findMatches(SymbolList text)
This will return an int[] giving the offsets of the matches in text
(ie the location of the first symbol of each match in the text ). |
protected int[] |
getKmpNextTable()
Returns the table of border lengths |
SymbolList |
getPattern()
|
static void |
main(java.lang.String[] args)
Demo and Test method |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
public KnuthMorrisPrattSearch(SymbolList pattern)
pattern
in text
using the
Knuth-Morris-Pratt algorithm.
A new class should be constructed for each occurance of
pattern
.
pattern
- the pattern to search forMethod Detail |
public int[] findMatches(SymbolList text)
text
(ie the location of the first symbol of each match in the text
).
text
- the text or sequence to search for the pattern
protected int[] getKmpNextTable()
public SymbolList getPattern()
public static void main(java.lang.String[] args) throws java.lang.Exception
args
- no arguments required
java.lang.Exception
- if the test fails
|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |