Monday, July 15, 2013

Knuth-Morris-Pratt substring search algorithm in LINQ

Surprisingly, I found no substring search algorithms in LINQ extension libraries like MoreLINQ or similar, so had to write own implementation of the known Knuth-Morris-Pratt method.
Some features are: linq lazy evaluation of input sequence, and special search version with precompiled failure table, which allows a bit faster search of the same substring in different input sequences.

The source code: