Diff Text Lines with a Longest Common Subsequence

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")
	}
}