Subject: Re: bug#77942: 31.0.50; replace-region-contents gets stuck

From: Paul Eggert <[email-masked]>
Date: Mon, 21 Apr 2025 15:32:17 -0700

On 4/21/25 14:11, Stefan Monnier wrote:
> Paul, IIUC you've played with this algorithm.  Would you be tempted to
> try and improve that situation where the replacement text is*much*
> smaller the text it replaces?

My quick reaction is that you'd need a different algorithm than the 
Myers-Ukkonen algorithm used by GNU diff etc. A good place to start 
might be here:

A. Andoni, R. Krauthgamer and K. Onak, "Polylogarithmic Approximation 
for Edit Distance and the Asymmetric Query Complexity," FOCS 2010, 
377-386, <https://doi.org/10.1109/FOCS.2010.43>.

... though this is just the tip of an iceberg that I haven't had time to 
look into. If there's real interest in this (it'd be some work) I can 
ask a colleague who's more of an expert....