func DiffChunks(a, b []string) []Chunk {
	alen, blen := len(a), len(b)  
	maxPath := alen + blen  
	if maxPath == 0 {
		return nil
	}
	endpoint := make([]int, 2*maxPath+1)  
	saved := make([][]int, 0, 8)  
	save := func() {
		dup := make([]int, len(endpoint))
		copy(dup, endpoint)
		saved = append(saved, dup)
	}
	var editDistance int  
dLoop:
	for editDistance = 0; editDistance <= maxPath; editDistance++ {
		for diag := -editDistance; diag <= editDistance; diag += 2 {  
			var aidx int  
			switch {
			case diag == -editDistance:
				aidx = endpoint[maxPath-editDistance+1] + 0
			case diag == editDistance:
				aidx = endpoint[maxPath+editDistance-1] + 1
			case endpoint[maxPath+diag+1] > endpoint[maxPath+diag-1]:
				aidx = endpoint[maxPath+diag+1] + 0
			default:
				aidx = endpoint[maxPath+diag-1] + 1
			}
			bidx := aidx - diag  
			for aidx < alen && bidx < blen && a[aidx] == b[bidx] {
				aidx++
				bidx++
			}
			endpoint[maxPath+diag] = aidx
			if aidx >= alen && bidx >= blen {
				save()  
				break dLoop
			}
		}
		save()  
	}
	if editDistance == 0 {
		return nil
	}
	chunks := make([]Chunk, editDistance+1)
	x, y := alen, blen
	for d := editDistance; d > 0; d-- {
		endpoint := saved[d]
		diag := x - y
		insert := diag == -d || (diag != d && endpoint[maxPath+diag-1] < endpoint[maxPath+diag+1])
		x1 := endpoint[maxPath+diag]
		var x0, xM, kk int
		if insert {
			kk = diag + 1
			x0 = endpoint[maxPath+kk]
			xM = x0
		} else {
			kk = diag - 1
			x0 = endpoint[maxPath+kk]
			xM = x0 + 1
		}
		y0 := x0 - kk
		var c Chunk
		if insert {
			c.Added = b[y0:][:1]
		} else {
			c.Deleted = a[x0:][:1]
		}
		if xM < x1 {
			c.Equal = a[xM:][:x1-xM]
		}
		x, y = x0, y0
		chunks[d] = c
	}
	if x > 0 {
		chunks[0].Equal = a[:x]
	}
	if chunks[0].empty() {
		chunks = chunks[1:]
	}
	if len(chunks) == 0 {
		return nil
	}
	return chunks
}
DiffChunks uses an O(D(N+M)) shortest-edit-script algorithm
to compute the edits required from A to B and returns the
edit chunks.
package diff
import (
	"fmt"
	"strings"
)
type Chunk struct {
	Added   []string
	Deleted []string
	Equal   []string
}
func (c *Chunk) empty() bool {
	return len(c.Added) == 0 && len(c.Deleted) == 0 && len(c.Equal) == 0
}
func Diff(A, B string) string {
	aLines := strings.Split(A, "\n")
	bLines := strings.Split(B, "\n")
	return Render(DiffChunks(aLines, bLines))
}
func Render(chunks []Chunk) string {
	buf := new(strings.Builder)
	for _, c := range chunks {
		for _, line := range c.Added {
			fmt.Fprintf(buf, "+%s\n", line)
		}
		for _, line := range c.Deleted {
			fmt.Fprintf(buf, "-%s\n", line)
		}
		for _, line := range c.Equal {
			fmt.Fprintf(buf, " %s\n", line)
		}
	}
	return strings.TrimRight(buf.String(), "\n")
}