String matching algorithms efficiently find patterns within text. The naive approach runs in O(n × m), but sophisticated algorithms achieve linear or near-linear time. KMP (Knuth-Morris-Pratt) precomputes a failure function (LPS array) to skip redundant comparisons, running in O(n + m). Rabin-Karp uses rolling hashes to compare windows in O(n + m) average time, excelling at multi-pattern search. The Z-Algorithm computes the Z-array storing longest prefix matches at each position, also running in O(n + m).
Backtracking systematically explores solution spaces by building candidates incrementally and pruning invalid branches. Classic applications include generating permutations and combinations, solving N-Queens and Sudoku, and finding all subsets. The Word Search problem combines backtracking with grid traversal. Branch-and-bound techniques like the minimum cost to cut a stick use interval DP with strategic pruning. Combination Sum variants handle items that can be used unlimited times versus once.
Bit manipulation unlocks elegant O(1) operations: checking powers of two with n & (n-1), counting set bits with Brian Kernighan's algorithm, and finding the unique element using XOR properties (since a^a = 0). The Boyer-Moore Voting algorithm finds the majority element in O(n) time and O(1) space. Misra-Gries generalizes this to find elements appearing more than n/k times. Other specialized techniques include Greedy algorithms with proof of optimality (activity selection, fractional knapsack, Huffman coding), Sweep Line for geometric problems, and Matrix Exponentiation for computing Fibonacci and linear recurrences in O(log n) time. Monotonic stacks and deques solve next-greater-element, daily temperatures, and sliding window extremes in linear time, while the Reservoir Sampling technique enables uniform random selection from streams of unknown size.