Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Hunt–Szymanski algorithm
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the Hunt–Szymanski algorithm, also known as Hunt–McIlroy algorithm, is a solution to the <a href="/facts/Longest_common_subsequence_problem/2HKIa0yd">longest common subsequence problem</a>. It was one of the first non-heuristic algorithms used in <a href="/facts/Diff/MtzRWwql">diff</a> which compares a pair of files each represented as a sequence of lines. To this day, variations of this algorithm are found in incremental <a href="/facts/Version_control_system/pxCmFXqK">version control systems</a>, <a href="/facts/Wiki_software/zNRxq6GV">wiki engines</a>, and <a href="/facts/Molecular_phylogenetics/FysplHP5">molecular phylogenetics</a> research software. </p><p>The worst-case complexity for this algorithm is <i>O</i>(<i>n</i>2 log <i>n</i>), but in practice <i>O</i>(<i>n</i> log <i>n</i>) is rather expected. </p>