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