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 O(n2 log n), but in practice O(n log n) 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 O(n2). The solution is modified so that there are lower time and space requirements for the algorithm when it is working with typical inputs.
Basic longest common subsequence solution
Algorithm Let Ai be the ith element of the first sequence. Let Bj be the jth element of the second sequence. Let Pij be the length of the longest common subsequence for the first i elements of A and the first j elements B.
P i j = { 0 if i = 0 or j = 0 , 1 + P i − 1 , j − 1 if A i = B j , max ( P i − 1 , j , P i , j − 1 ) if A i ≠ B j . {\displaystyle P_{ij}={\begin{cases}0&{\text{if}}\ i=0\ {\text{or}}\ j=0,\\1+P_{i-1,j-1}&{\text{if}}\ A_{i}=B_{j},\\\max(P_{i-1,j},P_{i,j-1})&{\text{if}}\ A_{i}\neq B_{j}.\end{cases}}}
Example
Consider the sequences A and B. A contains three elements:
A 1 = a , A 2 = b , A 3 = c . {\displaystyle {\begin{aligned}A_{1}=a,\\A_{2}=b,\\A_{3}=c.\end{aligned}}}
B contains three elements:
B 1 = a , B 2 = c , B 3 = b . {\displaystyle {\begin{aligned}B_{1}=a,\\B_{2}=c,\\B_{3}=b.\end{aligned}}}
The steps that the above algorithm would perform to determine the length of the longest common subsequence for both sequences are shown in the diagram. The algorithm correctly reports that the longest common subsequence of the two sequences is two elements long.
… excerpt ends here. Continue reading the full article.
