Hunt–Szymanski algorithm
In computer science, the Hunt–Szymanski algorithm, also known as Hunt–McIlroy algorithm, is a solution to the longest common subsequence problem. It was one of the first non-heuristic algorithms used in diff which compares a pair of files each represented as a sequence of lines. To this day, variations of this algorithm are found in incremental version control systems, wiki engines, and molecular phylogenetics research software. The worst-case complexity for this algorithm is , but in practice is rather expected. History The algorithm was proposed by Harold S. Stone as a generalization of a special case solved by Thomas G. Szymanski. James W. Hunt refined the idea, implemented the first version of the candidate-listing algorithm used by diff and embedded it into an older framework of Douglas McIlroy. The description of the algorithm appeared as a technical report by Hunt and McIlroy in 1976. The following year, a variant of the algorithm was finally published in a joint paper by Hunt and Szymanski. Algorithm The Hunt–Szymanski algorithm is a modification to a basic solution for the longest common subsequence problem which has complexity . The solution is modified so that there are lower time and space requirements for the algorithm when