Add notes on LCS weaknesses

1 files changed, 48 insertions, 0 deletions

diff --git a/text_diff_notes.md b/text_diff_notes.md
new file mode 100644
index 000000000..c4a183dea
--- /dev/null
+++ b/text_diff_notes.md
@@ -0,0 +1,48 @@
+Consider changing:
+
+```
+foo();
+bar();
+```
+
+To:
+
+```
+if (true) {
+  foo();
+}
+```
+
+What we want:
+
+```
++ if (true) {
+   foo();
+-  bar();
++ }
+```
+
+A longest-common-subsequence algorithm is wrong here. The longest
+subsequence is five tokens:
+
+```
+( ) ( ) ;
+```
+
+which leads to:
+
+```
++if+ (+true+) +{+
+   +foo+();
+    -bar-();
++}+
+```
+
+so we claim `foo` is added. We want the following *four* tokens to be
+preserved:
+
+```
+foo ( ) ;
+```
+
+Proposed solution: advance on both sides, keep first match.