next up previous contents index
Next: Score Matrix ( score_matrix Up: Alignment Data Types Previous: Alphabet ( alphabet )   Contents   Index


String Matching Algorithms ( string_matching )

Definition

An instance M of the data type string_matching is an object maintaining a pattern and a string. It provides a collection of different algorithms for computation of the exact string matching problem. Each function computes a list of all starting positions of occurences of the pattern in the string.
The algorithms can be called explicitly by their name or implicitly by making an algorithm the "current" algorithm (specified by the setAlgorithm-method) and using functions getFirstOccurence(), getNextOccurence(), and getAllOccurences().

Here is the list of the available parameters to specify the algorithm in the setAlgorithm(alg)-method. For each algorithm, the enumeration index gives the corresponding int that can be used in the setAlgorithm(int)-method in order to specify the algorithm.

  1. KARP$\_$RABIN
  2. MORRIS$\_$PRATT
  3. KNUTH$\_$MORRIS$\_$PRATT
  4. GALIL$\_$SEIFERAS
  5. BOYER$\_$MOORE
  6. TURBO$\_$BOYER$\_$MOORE
  7. TUNED$\_$BOYER$\_$MOORE
  8. ZHU$\_$TAKAOKA
  9. BERRY$\_$RAVINDRAN
  10. SMITH
  11. RAITA
  12. HORSPOOL
  13. BRUTE$\_$FORCE
  14. SHIFT$\_$OR
  15. REVERSE$\_$COLUSSI
  16. QUICK$\_$SEARCH
  17. REVERSE$\_$FACTOR
  18. TURBO$\_$REVERSE$\_$FACTOR
  19. OPTIMAL$\_$MISMATCH

Remark: This data type is experimental. It can significantly change in future versions.

#include < LEDA/string/string_matching.h >

Creation

string_matching M creates an instance M of type string_matching.

string_matching M(const string& s1, const string& s2)
    creates an instance M of type string_matching and initializes the pattern to s1 and the string to s2.

Operations

void M.setPattern(const string& str)
    sets the pattern to str.

void M.setString(const string& str)
    sets the string to str.

string M.getPattern() returns the pattern.

string M.getString() returns the string.

void M.setStrings(const string& str1, const string& str2)
    sets the pattern to str1 and the string to str2.

void M.setAlgorithm(alg A) sets the current algorithm to A (see table above).

void M.setAlgorithm(int A) sets the current algorithm to A by index (see table above).

list<int> M.getAllOccurences() executes the current algorithm reporting all occurences of the pattern in the string.

int M.getFirstOccurence() executes the current algorithm reporting the first occurence of the pattern in the string. If there is none, -1 is returned.

int M.getNextOccurence(int i) executes the current algorithm reporting the first occurence after position i of the pattern in the string. If there is none, -1 is returned. String positions start with 0.

list<int> M.getResult() returns the list of results after a computation.

void M.karp_rabin() applies the algorithm of Karp and Rabin.

void M.morris_pratt() applies the algorithm of Morris and Pratt.

void M.knuth_morris_pratt() applies the algorithm of Knuth, Morris and Pratt.

void M.galil_seiferas() applies the algorithm of Galil and Seiferas.

void M.boyer_moore() applies the algorithm of Boyer and Moore.

void M.turbo_boyer_moore() applies the turbo algorithm of Boyer and Moore.

void M.tuned_boyer_moore() applies the tuned algorithm of Boyer and Moore.

void M.zhu_takaoka() applies the algorithm of Zhu and Takaoka.

void M.berry_ravindran() applies the algorithm of Berry and Ravindran.

void M.smith() applies the algorithm of Smith.

void M.raita() applies the algorithm of Raita.

void M.horspool() applies the algorithm of Horspool.

void M.brute_force() applies the naive brute force algorithm.

void M.shift_or() applies the shift-or algorithm.

void M.reverse_colussi() applies the reverse colussi algorithm.

void M.quick_search() applies the quick search algorithm.

void M.reverse_factor() applies the reverse factor algorithm.

void M.turbo_reverse_factor() applies the turbo reverse colussi algorithm.

void M.optimal_mismatch() applies the optimal mismatch algorithm.


next up previous contents index
Next: Score Matrix ( score_matrix Up: Alignment Data Types Previous: Alphabet ( alphabet )   Contents   Index