Ask HN: I just wrote an O(N) diffing algorithm – what am I missing? 7 by keithwhor | 5 comments Hey folks, I've been building a rendering engine for a code editor the past couple of days. Rendering huge chunks of highlighted syntax can get laggy. It's not worth switching to React at this stage, so I wanted to just write a quick diff algorithm that would selectively update only changed lines. I found this article: https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ With a link to this paper, the initial Git diff implementation: http://www.xmailserver.org/diff2.pdf I couldn't find the PDF to start with, but read "edit graph" and immediately thought — why don't I just use a hashtable to store lines from LEFT_TEXT and references to where they are, then iterate over RIGHT_TEXT and return matches one by one, also making sure that I keep track of the last match to prevent jumbling? The algorithm I produced is only a few lines and seems accurate. It...