string-algorithmslisted

# String Algorithm Patterns This reference covers seven foundational string algorithms used in competitive programming and technical interviews. Each pattern includes recognition signals, a core idea explanation, a Python template, and notes on edge cases and common mistakes. Use the pattern recognition table to match problem constraints to the right technique, then drill into the individual pattern section. --- ## Pattern Recognition Table | Trigger Signals | Technique | Typical Complexity | |---|---|---| | Find pattern in text, exact match, prefix function | KMP | O(N + M) | | Longest common prefix at each position, string period | Z-function | O(N) | | Multiple pattern search, rolling hash, substring fingerprint | Rabin-Karp | O(N + M) average | | Longest palindromic substring, count palindromes | Manacher's | O(N) | | Fast substring comparison, equality checks in O(1) | String Hashing | O(N) preprocess, O(1) query | | Lexicographic ordering of suffixes, LCP queries, substring counting | Suffix Array | O(N log N) build | | Dictionary of patterns matched against text, multi-pattern search | Aho-Corasick | O(N + M + Z) | Where N = text length, M = pattern length (or total pattern lengths), Z = number of matches. --- ## Constraint-to-Technique Mapping - **Single pattern, exact match, N up to 10^6**: KMP or Z-function - **All prefix-suffix overlaps**: KMP failure function gives overlap chain - **String periodicity or repetition**: Z-function (period = smallest i where