Strings Algorithms

A string search that precomputes a failure function (LPS) so that, on a mismatch, it skips ahead instead of re-comparing the pattern from the start. It never rewinds the text pointer, matching in O(n+m).

A string search that compares hash values of the pattern and text windows. A rolling hash updates the window hash in O(1), and it only checks the actual characters when the hashes match — handy for multi-pattern search.

A search that compares the pattern from its right end and, on a mismatch, jumps the pattern far ahead using the bad-character rule. Skipping many text characters makes it one of the fastest single-pattern searches in practice.