Editing Longest common subsequence (section)

=== Reduce the problem set ===
The C matrix in the naive algorithm [[quadratic growth|grows quadratically]] with the lengths of the sequences.  For two 100-item sequences, a 10,000-item matrix would be needed, and 10,000 comparisons would need to be done.  In most real-world cases, especially source code diffs and patches, the beginnings and ends of files rarely change, and almost certainly not both at the same time.  If only a few items have changed in the middle of the sequence, the beginning and end can be eliminated.  This reduces not only the memory requirements for the matrix, but also the number of comparisons that must be done.

 '''function''' LCS(X[1..m], Y[1..n])
     start := 1
     m_end := m
     n_end := n
     ''trim off the matching items at the beginning''
     '''while''' start ≤ m_end '''and''' start ≤ n_end '''and''' X[start] = Y[start]
         start := start + 1
     ''trim off the matching items at the end''
     '''while''' start ≤ m_end '''and''' start ≤ n_end '''and''' X[m_end] = Y[n_end]
         m_end := m_end - 1
         n_end := n_end - 1
     C = array(start-1..m_end, start-1..n_end)
     ''only loop over the items that have changed''
     '''for''' i := start..m_end
         '''for''' j := start..n_end
             ''the algorithm continues as before ...''

In the best-case scenario, a sequence with no changes, this optimization would eliminate the need for the C matrix.  In the worst-case scenario, a change to the very first and last items in the sequence, only two additional comparisons are performed.