Cadena Algoritmo Referencia
Referencia para cadena algoritmos: search, editar distance, patrón matching, y compression.
Search Algorithms
Naive search checks every position (O(n*m) worst case). Knuth-Morris-Pratt (KMP) preprocesses the pattern for O(n+m) time. Boyer-Moore skips sections using bad character and good suffix heuristics, fast in practice. Rabin-Karp uses rolling hash for multiple pattern search. Aho-Corasick builds a finite automaton for multi-pattern matching in O(n) time. Suffix trees and arrays enable fast repeated search and various string problems. For most applications, built-in indexOf or regex is sufficient.
- KMP
- O(n+m) single pattern
- Boyer-Moore
- Fast in practice
- Aho-Corasick
- O(n) multi-pattern
preprocess patternskip heuristicsautomatonDistance and Similarity
Levenshtein distance counts insertions, deletions, and substitutions (edit distance). Damerau-Levenshtein adds transpositions (adjacent swaps). Hamming distance requires equal-length strings. Jaro and Jaro-Winkler similarity are designed for short strings (names). Longest Common Subsequence (LCS) finds the longest shared sequence. These algorithms enable fuzzy matching, spell checking, and DNA sequence analysis. Dynamic programming computes most in O(n*m) time and space (space can be optimized to O(min(n,m))).
- Levenshtein
- Insert/delete/substitute
- Jaro-Winkler
- Short string similarity
- LCS
- Longest common subseq
edit distancenamesdiff algorithm