The Hunt–McIlroy algorithm is a solution to the longest common subsequence problem

Longest common subsequence problem

The longest common subsequence problem is to find the longest subsequence common to all sequences in a set of sequences . Note that subsequence is different from a substring, see substring vs. subsequence...

. It was one of the first non-heuristic algorithms used in diff

Diff

In computing, diff is a file comparison utility that outputs the differences between two files. It is typically used to show the changes between one version of a file and a former version of the same file. Diff displays the changes made per line for text files. Modern implementations also...

. To this day, variations of this algorithm are found in incremental version control systems, wiki

Wiki

A wiki is a website that allows the creation and editing of any number of interlinked web pages via a web browser using a simplified markup language or a WYSIWYG text editor. Wikis are typically powered by wiki software and are often used collaboratively by multiple users. Examples include...

 engines, and molecular phylogenetics research software.

The research accompanying the final version of Unix

Unix

Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...

 diff

Diff

In computing, diff is a file comparison utility that outputs the differences between two files. It is typically used to show the changes between one version of a file and a former version of the same file. Diff displays the changes made per line for text files. Modern implementations also...

, written by Douglas McIlroy

Douglas McIlroy

Malcolm Douglas McIlroy is a mathematician, engineer, and programmer. As of 2007 he is an Adjunct Professor of Computer Science at Dartmouth College. Dr...

, was published in the 1976 paper "An Algorithm for Differential File Comparison", co-written with James W. Hunt, who developed an initial prototype of diff.

See also

• Levenshtein distance
  Levenshtein distance
  In information theory and computer science, the Levenshtein distance is a string metric for measuring the amount of difference between two sequences...
  
  
• Longest common subsequence problem
  Longest common subsequence problem
  The longest common subsequence problem is to find the longest subsequence common to all sequences in a set of sequences . Note that subsequence is different from a substring, see substring vs. subsequence...
  
  
• Wagner–Fischer algorithm
  Wagner–Fischer algorithm
  The Wagner–Fischer algorithm is a dynamic programming algorithm that measures the Levenshtein distance between two strings of characters.-Calculating distance:...