--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/goodjava/util/LineDiff.java	Sun May 12 15:25:29 2024 -0600
@@ -0,0 +1,90 @@
+package goodjava.util;
+
+import java.util.List;
+import java.util.ArrayList;
+import java.io.BufferedReader;
+import java.io.StringReader;
+import java.io.IOException;
+
+
+public final class LineDiff {
+	public static final char DELETE = '<';
+	public static final char INSERT = '>';
+
+	public static class Diff {
+		public final char operation;
+		public final int line;
+		public final String text;
+
+		private Diff(char operation,int line,String text) {
+			this.operation = operation;
+			this.line = line;
+			this.text = text;
+		}
+	}
+
+	public static String[] stringToLines(String s) {
+		List<String> list = new ArrayList<String>();
+		BufferedReader br = new BufferedReader(new StringReader(s));
+		String line;
+		try {
+			while( (line = br.readLine()) != null ) {
+				list.add(line);
+			}
+		} catch(IOException e) {
+			throw new RuntimeException(e);
+		}
+		return list.toArray(new String[list.size()]);
+	}
+
+	public static List<Diff> diff(String oldStr,String newStr) {
+		return diff( stringToLines(oldStr), stringToLines(newStr) );
+	}
+
+	// https://introcs.cs.princeton.edu/java/23recursion/Diff.java.html
+	public static List<Diff> diff(String[] oldLines,String[] newLines) {
+		List<Diff> diffs = new ArrayList<Diff>();
+
+		int nOld = oldLines.length;
+		int nNew = newLines.length;
+
+		// opt[iOld][iNew] = length of LCS of x[iOld..nOld] and y[iNew..nNew]
+		int[][] opt = new int[nOld+1][nNew+1];
+
+		// compute length of LCS and all subproblems via dynamic programming
+		for (int iOld = nOld-1; iOld >= 0; iOld--) {
+			for (int iNew = nNew-1; iNew >= 0; iNew--) {
+				if (oldLines[iOld].equals(newLines[iNew]))
+					opt[iOld][iNew] = opt[iOld+1][iNew+1] + 1;
+				else
+					opt[iOld][iNew] = Math.max(opt[iOld+1][iNew], opt[iOld][iNew+1]);
+			}
+		}
+
+		int iOld = 0, iNew = 0;
+		while (iOld < nOld && iNew < nNew) {
+			if (oldLines[iOld].equals(newLines[iNew])) {
+				iOld++;
+				iNew++;
+			} else if (opt[iOld+1][iNew] >= opt[iOld][iNew+1]) {
+				diffs.add( new Diff( DELETE, iOld+1, oldLines[iOld] ) );
+				iOld++;
+			} else {
+ 				diffs.add( new Diff( INSERT, iOld+1, newLines[iNew] ) );
+				iNew++;
+			}
+		}
+
+		// dump out one remainder of one string if the other is exhausted
+		while( iOld < nOld ) {
+			diffs.add( new Diff( DELETE, iOld+1, oldLines[iOld] ) );
+			iOld++;
+		}
+		while( iNew < nNew ) {
+			diffs.add( new Diff( INSERT, nOld+1, newLines[iNew] ) );
+			iNew++;
+		}
+
+		return diffs;
+	}
+}