Editing Diff (section)

== Algorithm ==
The operation of {{Mono|diff}} is based on solving the [[longest common subsequence problem]].<ref name="diff paper" />

In this problem, given two sequences of items:

 {{underline|a}} {{underline|b}} {{underline|c}} {{underline|d}} {{underline|f}} {{underline|g}} h {{underline|j}} q {{underline|z}}

 {{underline|a}} {{underline|b}} {{underline|c}} {{underline|d}} e {{underline|f}} {{underline|g}} i {{underline|j}} k r x y {{underline|z}}

and we want to find a longest sequence of items that is present in both original sequences in the same order. That is, we want to find a new sequence which can be obtained from the first original sequence by deleting some items, and from the second original sequence by deleting other items. We also want this sequence to be as long as possible. In this case it is

 a b c d  f  g  j  z

From a longest common subsequence it is only a small step to get {{Mono|diff}}-like output: if an item is absent in the subsequence but present in the first original sequence, it must have been deleted (as indicated by the '-' marks, below). If it is absent in the subsequence but present in the second original sequence, it must have been inserted (as indicated by the '+' marks).

 e   h i   q   k r x y
 +   - +   -   + + + +