https://en.wikipedia.org/wiki/Gosling_Emacs
>Gosling Emacs was especially noteworthy because of the effective redisplay code, which used a dynamic programming technique to solve the classical string-to-string correction problem. The algorithm was quite sophisticated; that section of the source was headed by a skull-and-crossbones in ASCII art, warning any would-be improver that even if they thought they understood how the display code worked, they probably did not.
https://donhopkins.com/home/archive/emacs/skull-and-crossbon...
Trivia: That "Skull and Crossbones" ASCII art is originally from Brian Reid's Scribe program, and is not copyrighted.
https://donhopkins.com/home/archive/emacs/mw/display.c
/* 1 2 3 4 .... Each Mij represents the minumum cost of
+---+---+---+---+----- rearranging the first i lines to map onto
1 | | | | | the first j lines (the j direction
+---+---+---+---+----- represents the desired contents of a line,
2 | | \| ^ | | i the current contents). The algorithm
+---+---\-|-+---+----- used is a dynamic programming one, where
3 | | <-+Mij| | M[i,j] = min( M[i-1,j],
+---+---+---+---+----- M[i,j-1]+redraw cost for j,2
4 | | | | | M[i-1,j-1]+the cost of
+---+---+---+---+----- converting line i to line j);
. | | | | | Line i can be converted to line j by either
. just drawing j, or if they match, by moving
. line i to line j (with insert/delete line)
*/
https://dl.acm.org/doi/10.1145/1159890.806463
A redisplay algorithm, by James Gosling.
Abstract
This paper presents an algorithm for updating the image displayed on a conventional video terminal. It assumes that the terminal is capable of doing the usual insert/delete line and insert/delete character operations. It takes as input a description of the image currently on the screen and a description of the new image desired and produces a series of operations to do the desired transformation in a near-optimal manner. The algorithm is interesting because it applies results from the theoretical string-to-string correction problem (a generalization of the problem of finding a longest common subsequence), to a problem that is usually approached with crude ad-hoc techniques.
[...]
6. Conclusion
The redisplay algorithm described in this paper is used in an Emacs-like editor for Unix and a structure editor. It's performance has been quite good: to redraw everything on the screen (when everything has changed) takes about 0.12 seconds CPU time on a VAX 11/780 running Unix. Using the standard file typing program, about 0.025 seconds of CPU time are needed to type one screenful of text. Emacs averages about 0.004 CPU seconds per keystroke (with one call on the redisplay per keystroke).
Although in the interests of efficency we have stripped down algorithm 5 to algorithm 6 the result is still an algorithm which has a firm theoretical basis and which is superior to the usual ad-hoc approach.