Galil-Seiferas

Linear algorithm using constant extra space complexity. Preprocessing in $O(m)$-time. It performs $5n$ text character comparisons in the worst case.

Appeared in:

• [60]: Galil, Z., Seiferas, J.I.: Time-space-optimal string matching. In: Proceedings of the 13th Annual ACM Symposium on Theory of Computing, May 11-13, 1981, Milwaukee, Wisconsin, USA. pp. 106–113. ACM (1981), http://doi.acm.org/10.1145/800076.802463 ↗
• [61]: Galil, Z., Seiferas, J.I.: Time-space-optimal string matching. J. Comput. Syst. Sci. 26(3), 280–294 (1983), http://dx.doi.org/10.1016/0022-0000(83)90002-8 ↗