Comparison Mode
Side-by-side: use case, requirements, complexity, strengths, weaknesses, example problems, and a clear “choose this when…”.
BFS vs DFSDijkstra vs Bellman-FordKruskal vs PrimMerge Sort vs Quick SortHeap vs Priority QueueHash Map vs Tree MapBFS vs DijkstraSliding Window vs Two PointersPrefix Sum vs Segment TreeGreedy vs Dynamic ProgrammingMemoization vs TabulationTarjan vs KosarajuSegment Tree vs Fenwick TreeArray vs Linked ListStack vs QueueQuick Sort vs Heap SortKMP vs Rabin-KarpUnion-Find vs DFSTrie vs Hash MapAVL Tree vs Red-Black Tree
KMPStrings | Rabin-KarpStrings | |
|---|---|---|
| Use case | Find one pattern in a text deterministically in linear time. | Find one or many patterns by comparing rolling hashes; substring fingerprinting. |
| Requirements | The failure (LPS) table of the pattern. | A rolling hash with a modulus and base; a hash set of pattern hashes for multiple patterns. |
| Time complexity | O(n + m) worst case. | Expected O(n + m); worst O(n * m) with many collisions. |
| Space complexity | O(m) for the table. | O(1) per pattern hash (plus the set for multiple patterns). |
| Strengths | Guaranteed linear; never re-reads text characters; the failure table itself solves prefix/suffix problems. | Simple to write; extends naturally to many patterns, 2D matching and duplicate-substring detection. |
| Weaknesses | One pattern at a time; the table construction is fiddly to write under pressure. | Probabilistic unless matches are verified; collisions can be engineered against a fixed modulus. |
| Example problems | Implement strStr, shortest palindrome, repeated substring pattern. | Repeated DNA sequences, longest duplicate substring, implement strStr. |
| Choose this when | Choose KMP when you need a deterministic linear-time single-pattern search or need the prefix function itself. | Choose Rabin-Karp when searching for many patterns of the same length, comparing many substrings, or when simplicity beats determinism. |