> Nope. Naive approach is: for every byte of the modified file, compare against every position in the source file and find the longest match. If less than the c

> Nope. Naive approach is: for every byte of the modified file, compare against every position in the source file and find the longest match. If less than the cost of encoding the pointer+length pair, then add it to a queue of raw bytes to write. Flush the queue whenever you find a long enough match. That is of course O(n×m), which is easier to just say O(n^2). > > Tried exploring string-search algorithms like Knuth-Morris-Pratt and Boyer-Moore; tried keeping a tree list of 16-bit matches (which in fully randomized data reduces search overhead to O(n×m/{between log2(65536) and 65536}) ... but in a file of nothing but null bytes slightly hurts performance), tried skipping by S bytes per compare and then backtracking when long enough matches are found (hurts patch size efficiency as N goes up, but reduces overhead by O(n×m/S), and so on. A helpful idea is first to consider what you consider as the "correct" alignment. Often the Levenshtein distance (https://en.wikipedia.org/wiki/Levenshtein_distance https://en.wikipedia.org/wiki/Levenshtein_distance) is used and an alignment is considered as proper if the number of necessary steps (insertion/deletion/replacement of 1 character) equals to the Levenshtein distance. Obviously this does not necessary define a unique alignment (consider "a" - "aa" or "ab" - "ba"). An idea that I find interesting to consider is whether you could construct a o(m * n) (i. e. asymptotically faster than O(m * n)) algorithm that computes k elementary operations (insertion/deletion/replacement of 1 character) that convert the first string s into the second string s' such that there exists a fixed constant 1 < C with k <= C * d(s, s'), where d(s, s') is the Levenshtein distance between s and s'. How small can you get C? I really don't know the answer (I haven't even thought much about it), but perhaps this idea is helpful to you?