基于最长公共子序列的文本行比较

功能说明

这段代码按行比较两个文本版本，输出类似 diff 的操作序列：空格前缀表示两边相同的行，- 表示只在左侧存在的行，+ 表示只在右侧存在的行。它适合配置变更预览、日志版本对比或代码审查工具的最小示例。

实现基于最长公共子序列（LCS）：先填一张动态规划表，记录每个后缀能匹配的最长行数，再从左上角回溯，决定当前行是保留、删除还是新增。

关键代码

diffLines 创建 (len(left)+1) x (len(right)+1) 的整数表。从右下往左上填表：两行相同则取对角线加一，否则取下方和右方中较大的值。这样 table[i][j] 表示从 i、j 开始的最长公共子序列长度。

回溯时，相同行输出 ' ' 并同时前进；否则比较下方和右方，选择能保留更多匹配的方向，输出删除或新增。循环结束后，把任一侧剩余的行全部输出。

使用注意

LCS 的时间和空间复杂度都是 O(n*m)，大文件会消耗大量内存。生产环境应使用 Myers、patience 或 histogram 等更高效算法，并限制最大行数和单行长度。这里按整行精确比较，不做空白忽略或行内字符级 diff。

当两侧都有多种等价匹配时，代码用 >= 固定选择“先删除后新增”，因此输出确定，但不一定是最小编辑脚本。Op.Kind 使用单字节标记，若要输出带上下文的 unified diff，还需要分组和行号计算。

验证方式

示例左侧为 alpha/beta/gamma/delta，右侧把 beta 改为 beta changed 并追加 epsilon。输出包含 3 行不变、1 行删除、2 行新增，代码断言 added == 2、removed == 1。可以把左右完全对调，确认新增和删除计数互换。

代码示例

package main

import (
	"fmt"
	"strings"
)

type Op struct {
	Kind byte
	Line string
}

func diffLines(left, right []string) []Op {
	rows := len(left) + 1
	columns := len(right) + 1
	table := make([][]int, rows)
	for index := range table {
		table[index] = make([]int, columns)
	}

	for i := len(left) - 1; i >= 0; i-- {
		for j := len(right) - 1; j >= 0; j-- {
			if left[i] == right[j] {
				table[i][j] = table[i+1][j+1] + 1
			} else if table[i+1][j] >= table[i][j+1] {
				table[i][j] = table[i+1][j]
			} else {
				table[i][j] = table[i][j+1]
			}
		}
	}

	var operations []Op
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		switch {
		case left[i] == right[j]:
			operations = append(operations, Op{' ', left[i]})
			i++
			j++
		case table[i+1][j] >= table[i][j+1]:
			operations = append(operations, Op{'-', left[i]})
			i++
		default:
			operations = append(operations, Op{'+', right[j]})
			j++
		}
	}
	for ; i < len(left); i++ {
		operations = append(operations, Op{'-', left[i]})
	}
	for ; j < len(right); j++ {
		operations = append(operations, Op{'+', right[j]})
	}
	return operations
}

func render(operations []Op) string {
	var builder strings.Builder
	for _, operation := range operations {
		fmt.Fprintf(&builder, "%c %s\n", operation.Kind, operation.Line)
	}
	return builder.String()
}

func main() {
	left := strings.Split("alpha\nbeta\ngamma\ndelta", "\n")
	right := strings.Split("alpha\nbeta changed\ngamma\ndelta\nepsilon", "\n")
	operations := diffLines(left, right)
	fmt.Print(render(operations))

	added, removed := 0, 0
	for _, operation := range operations {
		switch operation.Kind {
		case '+':
			added++
		case '-':
			removed++
		}
	}
	if added != 2 || removed != 1 {
		panic("unexpected diff counts")
	}
}