String Matching algorithm¶

Fast access linear time string matching algorithm from Knuth, Morris and Pratt. Mathematical complexity: \(O(m + n)\), where n is the length of the sequence and m is the length of query string.

The algorithm avoids the computation of transition function delta altogether (better than using a finite automata).