86algos

exact string matching algorithms

In the following table the comprehensive list of all string matching algorithms presented since 1970 is presented. All the algorithms listed below are implemented in smart. For each algorithm a list of all versions implemented in smart is reported on the right. To test the correspondent version of the algorithm in smart simply select the version name.
For example use the command ./select bf to select the Brute Force algorithm.
By following the links on the name oof the algorithms you can find a page with details and bibliographic references. By following the links on the name of the versions you can find a page with the correspondent C code.

name code var. ref. year
Ahmed Kaykobad Chowdhuryakc
2003
Alpha Skip Searchaskip
1998
Apostolico Crochemoreac
1991
Apostolico Giancarloag
1986
Average Optimal Shift Oraoso2
[+2] 2005
BNDM with Extended Shiftbxs
[+5] 2010
Backward DAWG Matchingbdm
1994
Backward Fast Search, Fast Boyer Moorebfs
2004
Backward Nondeterministic DAWG Matchingbndml
[+1] 1998
Backward Nondeterministic DAWG Matching for long patternslbndm
2003
Backward Nondeterministic DAWG Matching with Horspool Shiftsbndm-bmh
2005
Backward Nondeterministic DAWG Matching with loop unrollingbndmq2
2005
Backward Nondeterministic DAWG Matching with q-gramsbndmq2
[+2] 2009
Backward Oracle Matchingbom
1999
Backward SNR DAWG Matchingbsdm
[+7] 2012
Berry Ravindranbr
1999
Bit Parallel Length Invariant Matcherblim
2008
Bit Parallel Wide Window2bpww2
2010
Bit Parallel2 Wide Windowbp2ww
2010
Bitparallel Wide Windowbww
2005
Boyer Moorebm
1977
Boyer Moore Horspoolusing Probabilitiespbmh
2006
Brute Forcebf
Colussicol
1991
Crochemore-Perrin algorithm using SSE instructionsssecp
2011
Deterministic Finite Automatonaut
Double Forward DAWG Matchingdfdm
2000
Exact Packed String Matching algorithmepsm
2013
Extended Backward Oracle Matchingebom
2009
Factorized Backward Nondeterministic DAWG Matchingkbndm
2010
Factorized Shift Andksa
2010
Fast Average Optimal Shift Orfaoso2
[+2] 2005
Fast Searchfs
[+4] 2003
Forward Backward Oracle Matchingfbom
2009
Forward DAWG Matchingfdm
1994
Forward Fast Searchffs
2004
Forward Nondeterministic DAWG Matchingfndm
2005
Forward Simplified BNDM using q-grams and s-forward charactersfsbndm20
[+13] 2011
Forward Simplified Backward Nondeterministic DAWG Matchingfsbndm
[+4] 2009
Franek Jennings Smythfjs
2007
Galil Giancarlogg
1992
Genomic Rapid Algofor String Pattern Matchinggraspm
2009
Horspoolhor
1980
Horspool with BNDM testbmh-sbndm
2005
Improved Linear DAWG Matchingildm1
2006
Improved Linear DAWG Matching 2ildm2
2006
KMP Skip Searchkmpskip
1998
Karp Rabinkr
1987
Knuth Morris-Prattkmp
1977
Linear DAWG Matchingldm
2005
Maximal Shiftms
1990
Morris Prattmp
1970
Not So Naivensn
1993
Optimal Mismatchom
1990
Quick Searchqs
1990
Raitaraita
1992
Reverse Colussircol
1994
Reverse Factorrf
1992
SSABSssabs
2004
SSEFssef
2009
Shift Andsa
1992
Shift Orso
1992
Shift Or with q-gramsufndmq2
[+3] 2009
Shift Vector Matchingsvm0
[+4] 2003
Simonsimon
1993
Simplified BNDM with loop unrollingsbndm2
2005
Simplified Backward Nondeterministic DAWG Matchingsbndm
[+3] 2003
Simplified Backward Nondeterministic DAWG Matching with q-gramssbndmq2
[+3] 2009
Simplified Extended Backward Oracle Matchingsebom
2009
Simplified Forward Backward Oracle Matchingsfbom
2009
Skip Searchskip
1998
Small Alphabet Bit Parallelsabp
2009
Smithsmith
1991
String Matching on Ordered ALphabetsmoa
1992
Succint Backward DAWG Matchingsbdm
2009
TVSBStvsbs
[+4] 2006
Tailed Substringts
2004
Tuned Boyer Mooretunedbm
1991
Turbo Boyer Mooretbm
1994
Turbo Reverse Factortrf
1994
Two Sliding Windowtsw
2008
Two Waytw
1991
Two-Way Nondeterministic DAWG Matchingtndm
[+1] 2003
Wide Windowww
2005
Wu Manber for Single Pattern Matchinghash3
[+2] 2007
Zhu Takaokazt
1987