Hunt–Szymanski algorithm
From Wikipedia, the free encyclopedia
In computer science, the Hunt–Szymanski algorithm,[1][2] 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 O(n2 log n), but in practice O(n log n) is rather expected.[3][4]