Wide Window

Combination of Forward-DAWG-Matching and Reverse-Factor. It uses the suffix automaton of the pattern and the prefix automaton of the reverse of the pattern. It has a linear worst case time complexity.

Appeared in:

• [63]: He, L., Fang, B., Sui, J.: The wide window string matching algorithm. Theor. Comput. Sci. 332(1-3), 391–404 (2005), http://dx.doi.org/10.1016/j.tcs.2004.12.002 ↗