String matching is a deep subfield with its own family of algorithms. The Knuth-Morris-Pratt algorithm searches for occurrences of a word W within a text S by exploiting the structure of the pattern itself, so that when a mismatch occurs, the word embodies enough information to determine where the next match could begin. The Rabin-Karp algorithm uses hashing to find any one of a set of pattern strings in a text, achieving average and best case \(O(n+m)\) but worst case \(O(nm)\). The Z-algorithm is a linear-time string matching algorithm that constructs a Z-array whose entry at position i is the length of the longest common prefix between the string and its suffix starting at i, while the Aho-Corasick algorithm constructs a finite state machine from a set of pattern strings and locates all occurrences of any of them in a text. Manacher's algorithm finds the longest palindromic substring of a string in linear time \(O(n)\), and the Boyer-Moore string search algorithm efficiently skips sections of the text using two heuristics: the bad character rule and the good suffix rule. For more complex queries on texts, a suffix tree is a compressed trie of all suffixes of a string and is a powerful structure for problems like pattern matching and longest repeated substring, while a suffix array is a sorted array of all suffixes and offers a more space-efficient alternative.
Beyond exact matching, several measures quantify the similarity or distance between sequences and other objects. The Levenshtein distance, or edit distance, counts the minimum number of insertions, deletions, and substitutions to transform one string into another, while the Hamming distance only allows substitutions and requires strings of equal length. Jaccard similarity measures the similarity between two sets as the size of their intersection divided by the size of their union, and cosine similarity measures the similarity between two non-zero vectors as the cosine of the angle between them. For geometric points, Euclidean distance is the straight-line distance between two points, and Manhattan distance is the distance measured along axes at right angles in a grid-like fashion. In data compression, Huffman coding assigns variable-length codes to input characters based on their frequencies, while arithmetic coding encodes the entire message into a single number in \([0, 1)\) and is generally more efficient but more complex. Run-length encoding stores runs of identical values as a single value and count, and the Burrows-Wheeler Transform rearranges a string into runs of similar characters as a preprocessing step for compression algorithms like bzip2. At the lowest level, bit manipulation algorithmically manipulates bits using the operators AND (&), OR (|), XOR (^), NOT (~), Left Shift (<<), and Right Shift (>>).
Underneath all of these algorithms lies a theoretical framework of complexity and a layer of systems concerns. The complexity class P contains decision problems solvable by a deterministic Turing machine in polynomial time, while NP contains problems verifiable in polynomial time. A problem is NP-complete if it is in NP and every other problem in NP can be reduced to it in polynomial time, making these the hardest problems in NP. A problem is NP-hard if every problem in NP can be reduced to it in polynomial time, but it need not itself be in NP. Probabilistic and randomized algorithms come in two main flavors: Monte Carlo algorithms may produce an incorrect result with small probability, and running them more times reduces that error, while Las Vegas algorithms always produce a correct result, but their running time is a random variable. In game theory and AI, the minimax algorithm minimizes the possible loss for a worst case, and alpha-beta pruning decreases the number of nodes evaluated by minimax. Cache replacement policies include LRU, which discards the least recently used item first, and LFU, which discards the least frequently used item. The CAP theorem states that a distributed data store can simultaneously provide only two of Consistency, Availability, and Partition Tolerance. Database durability and atomicity are commonly ensured by write-ahead logging, in which modifications are written to a log before being applied to the main database, and by shadow paging, which maintains a current and a shadow page table and switches them at commit. The simplex algorithm is a popular method for linear programming that moves along the edges of the feasible region, a polytope, to find the optimal solution. In concurrent systems, a race condition occurs when threads access shared data concurrently with results depending on execution order, a deadlock occurs when each process holds a resource and waits for one held by another, and a livelock is similar but the states of the processes constantly change without any progressing. Synchronization primitives include a mutex, which is a locking mechanism allowing only one owner, and a semaphore, which is a signaling mechanism permitting N simultaneous accesses. Compare-And-Swap is an atomic instruction that compares a memory location to an expected value and only updates it if they match, but it can suffer from the ABA problem when a value changes from A to B and back to A. False sharing occurs when threads on different processors modify variables that share a cache line. At the hardware level, branch prediction guesses the direction of a branch to keep the instruction pipeline full, and endianness describes the byte order in a word: big-endian stores the most significant byte at the smallest address, and little-endian stores the least significant. Finally, mark and sweep is a two-phase garbage collection algorithm that first marks all reachable objects and then sweeps away unmarked ones, completing the bridge from pure algorithmic theory to the systems in which those algorithms run.