LCS
siglaprogramação
Significa: longest common subsequence
A maior sequência comum a duas entradas, preservando a ordem.
A maior subsequência comum (do inglês longest common subsequence) é a base da maioria das ferramentas de diff: a maior sequência ordenada (mas não necessariamente contígua) de elementos compartilhada por dois arquivos. O que sobra vira as adições e remoções que um diff mostra.
A maior subsequência comum é a sequência mais longa de elementos que aparecem na mesma ordem em duas entradas, ainda que não de forma adjacente. É o algoritmo por trás de todo diff que você já leu.
Entendê-lo explica por que diffs às vezes parecem errados. O algoritmo encontra um roteiro mínimo de edição, e não a mudança que um humano fez, então mover um bloco de código aparece como remoção e inserção, e uma pequena edição dentro de uma região repetitiva pode alinhar contra a instância errada e produzir um trecho confuso. Ferramentas modernas acrescentam heurísticas exatamente por isso, e conhecer o algoritmo subjacente é o que torna um diff estranho explicável em vez de misterioso.
Também conhecido como: lcs