Function hirschbergDiff

diff/lcs.go:53–93

hirschbergDiff recursively computes the LCS-based diff in linear space. The algorithm splits seq1 in half, finds the optimal split point in seq2 using forward and backward LCS score rows, then recurses on each half. At each recursion level only O(len(seq2)) extra space is used.

(seq1, seq2 []string)

// using forward and backward LCS score rows, then recurses on each half.
// At each recursion level only O(len(seq2)) extra space is used.
func hirschbergDiff(seq1, seq2 []string) []difflib.DiffRecord {
	n, m := len(seq1), len(seq2)

	if n == 0 {
		result := make([]difflib.DiffRecord, m)
		for i, s := range seq2 {
			result[i] = difflib.DiffRecord{Payload: s, Delta: difflib.RightOnly}
		}
		return result
	}
	if m == 0 {
		result := make([]difflib.DiffRecord, n)
		for i, s := range seq1 {
			result[i] = difflib.DiffRecord{Payload: s, Delta: difflib.LeftOnly}
		}
		return result
	}
	if n == 1 {
		return singleRowDiff(seq1[0], seq2)
	}

	mid := n / 2

	forward := lcsLift(seq1[:mid], seq2)
	backward := lcsLiftSuffix(seq1[mid:], seq2)

	splitJ := 0
	maxScore := -1
	for j := 0; j <= m; j++ {
		score := forward[j] + backward[j]
		if score > maxScore {
			maxScore = score
			splitJ = j
		}
	}

	left := hirschbergDiff(seq1[:mid], seq2[:splitJ])
	right := hirschbergDiff(seq1[mid:], seq2[splitJ:])

	return append(left, right...)
}

// singleRowDiff handles the base case where seq1 has exactly one element.
// It matches difflib.Diff's behavior which prefers LeftOnly and matches