Strings

String algorithms are techniques for working with text efficiently, with pattern matching (finding where a word occurs inside a longer text) as the classic example. The naive approach tries every starting position and compares character by character, which wastes work re-reading text it already checked. KMP avoids this by precomputing, for each prefix of the pattern, how much of it can be reused after a mismatch, so it never steps backward in the text. Rabin–Karp instead compares hashes of the pattern and a window of text, updating the window’s hash cheaply as it slides one character. Many everyday string problems also lean on character counts and hashing.