Skip to content
Exact Online String Matching

Chronology of Exact Online String Matching Algorithms

Since 1970 more than 120 string matching algorithms have been proposed. In this diagram shown almost all of them. The list is updated to May 2016. From Exact Online String Matching Bibliography

Try: zoom, drag diagram below 👇 or hover, click nodes.

timeline 0 1970 1970 1977 1977 1980 1980 1981 1981 1986 1986 1987 1987 1989 1989 1990 1990 1991 1991 1992 1992 1993 1993 1994 1994 1998 1998 1999 1999 2000 2000 2002 2002 2003 2003 2004 2004 2005 2005 2006 2006 2007 2007 2008 2008 2009 2009 2010 2010 2011 2011 2012 2012 2013 2013 2014 2014 2015 2015 2016 2016 DFA DFA SA SA DFA->SA SO SO DFA->SO RF RF DFA->RF SIM SIM DFA->SIM LDM LDM DFA->LDM KSA KSA DFA->KSA BF BF MP MP BF->MP BM BM BF->BM NSN NSN BF->NSN TS TS BF->TS KMP KMP MP->KMP KMPS KMPS MP->KMPS HOR HOR BM->HOR AG AG BM->AG BM->RF TBM TBM BM->TBM RCOL RCOL BM->RCOL SVM SVM BM->SVM FS FS BM->FS BFS BFS BM->BFS 2BLOCK 2BLOCK BM->2BLOCK BBM BBM BM->BBM MSBM MSBM BM->MSBM MSH MSH BM->MSH AC AC KMP->AC COL COL KMP->COL KMP->KMPS FJS FJS KMP->FJS PSS PSS KMP->PSS ZT ZT HOR->ZT QS QS HOR->QS SMITH SMITH HOR->SMITH TunBM TunBM HOR->TunBM RAITA RAITA HOR->RAITA HOR->BFS HOR->TS BNDMBMH BNDMBMH HOR->BNDMBMH BMHBNDM BMHBNDM HOR->BMHBNDM PBMH PBMH HOR->PBMH HASHq HASHq HOR->HASHq BMHq BMHq HOR->BMHq GRASPm GRASPm HOR->GRASPm HOR->MSBM HOR->MSH IOM IOM HOR->IOM WOM WOM HOR->WOM SSM SSM HOR->SSM GS GS AKC AKC AG->AKC KR KR BR BR ZT->BR TSA TSA SA->TSA TSAq TSAq SA->TSAq AOSO AOSO SO->AOSO TSO TSO SO->TSO TSOq TSOq SO->TSOq MS MS OM OM OM->PBMH QS->MS QS->OM QS->SMITH QS->BR FFS FFS QS->FFS SSABS SSABS QS->SSABS QS->FJS FBOM FBOM QS->FBOM TSW TSW QS->TSW QLQS QLQS QS->QLQS GG GG COL->GG COL->RCOL TW TW SSECP SSECP TW->SSECP BDM BDM RF->BDM TRF TRF RF->TRF BOM BOM RF->BOM WW WW RF->WW RAITA->SSABS SMOA SMOA BNDM BNDM BDM->BNDM BDM->LDM SBDM SBDM BDM->SBDM BSDM BSDM BDM->BSDM FDM FDM DFDM DFDM FDM->DFDM FDM->WW FNDM FNDM FDM->FNDM BNDML BNDML BNDM->BNDML BNDM2 BNDM2 BNDM->BNDM2 LBNDM LBNDM BNDM->LBNDM SBNDM SBNDM BNDM->SBNDM TNDM TNDM BNDM->TNDM BNDM->BNDMBMH BNDM->BMHBNDM BNDMq BNDMq BNDM->BNDMq BXS BXS BNDM->BXS BQL BQL BNDM->BQL KBNDM KBNDM BNDM->KBNDM ASKIP ASKIP SKIP SKIP SKIP->ASKIP SKIP->KMPS SSEF SSEF SKIP->SSEF SKIPq SKIPq SKIP->SKIPq EBOM EBOM BOM->EBOM TVSBS TVSBS BR->TVSBS RSA RSA BR->RSA ETSW ETSW BR->ETSW JOM JOM BR->JOM SAS SAS SBNDM2 SBNDM2 SBNDM->SBNDM2 FSBNDM FSBNDM SBNDM->FSBNDM SBNDMq SBNDMq SBNDM->SBNDMq SBNDMw SBNDMw SBNDM->SBNDMw FS->FFS BoFS BoFS FS->BoFS FSw FSw FS->FSw BFFS BFFS FFS->BFFS SSABS->TVSBS ILDM2 ILDM2 LDM->ILDM2 ILDM1 ILDM1 LDM->ILDM1 BWW BWW WW->BWW BPWW2 BPWW2 WW->BPWW2 BP2WW BP2WW WW->BP2WW FAOSO FAOSO AOSO->FAOSO UFNDMq UFNDMq FNDM->UFNDMq TVSBSw TVSBSw TVSBS->TVSBSw MHASHq MHASHq HASHq->MHASHq HASHq->SKIPq EBOM->FBOM SEBOM SEBOM EBOM->SEBOM FBNDM FBNDM FBOM->FBNDM SFBOM SFBOM FBOM->SFBOM BLIM BLIM FBNDM->FSBNDM FSBNDMqf FSBNDMqf FSBNDM->FSBNDMqf FSBNDMw FSBNDMw FSBNDM->FSBNDMw TSW->ETSW ERSA ERSA TSW->ERSA SABP SABP EPSM EPSM SSEF->EPSM QF QF PBR PBR PB PB BSDMqx BSDMqx BSDM->BSDMqx RSA->ERSA EERSA EERSA ETSW->EERSA ERSA->EERSA FSW FSW ERSA->FSW BSDMqxw BSDMqxw BSDMqx->BSDMqxw

About demo

This demo is to show the potential of modern Jamstack and alternative ideas for publishing Second Brain / Digital Garden.

Markdown as “graph” database

  • Data for timeline directly queried from markdown files. No need to maintain a separate file.
  • Connection between nodes automatically discovered based on links (markdown links or wiki links).

No JS diagram

  • Diagram fully generated on the server (at build time in case of Jamstack). So it works even without JS - no need for Mermaid or d3 on the client
  • Diagram is embedded SVG, which allows
    • to add HTML links to it
    • style it with CSS classes, for example, to add dark theme support

Progressively enhanced diagram

On top of static SVG, there is a small JS added to:

  • to allow drag/zoom diagram
  • to show HTML reach snippets when the user hovers over a node
    • snippet is HTML page generated based on markdown from the file

Technology