Skip to content
Exact Online String Matching

Double Forward DAWG Matching

Modification of Forward-DAWG-Matching. It works in linear worst case time using a DAWG of the pattern and a DAWG of the reverse of the pattern.

Appeared in:

  • [4]: Allauzen, C., Raffinot, M.: Simple optimal string matching algorithm. In: Giancarlo, R., Sankoff, D. (eds.) Combinatorial Pattern Matching, 11th Annual Symposium, CPM 2000, Montreal, Canada, June 21-23, 2000, Proceedings. Lecture Notes in Computer Science, vol. 1848, pp. 364–374. Springer (2000), http://dx.doi.org/10.1007/3-540-45123-4_30 ↗
  • [5]: Allauzen, C., Raffinot, M.: Simple optimal string matching algorithm. J. Algorithms 36(1), 102–116 (2000), http://dx.doi.org/10.1006/jagm.2000.1087 ↗