我有一个多行文本的UTF-8字符串。我对它执行一些预处理，改变长度和添加/删除字符。
将rn替换为n。
如何将新字符串中的位置与旧字符串中的位置相关联，以便我的代码能够显示"位置x的语法无效";这个位置会在原始字符串中所以用户不会有问题找到触发错误的字符?
听起来你从不添加/删除行。因此，这是一个更简单的问题，"将一行中的旧字符位置映射到新字符位置"，L行对应L次。
从一行N个字符开始，并对其进行更改。初始化一个矢量idx，计数从0 ..n - 1,表示第i个"new"字符对应旧字符i。将文本更新描述为
- 删除J处的K个字符
- 在J处插入K字符
- 在J 处替换K个字符
只有前两个影响idx。
删除时，在删除的索引上写NULL墓碑剩余idx项减k
插入时则相反，将项增加K。决定新条目应该具有什么值是一个难题J(重复)可能是最有意义的价值为您的应用程序。
也许你一直在使用字符串比较，也许是一个正则表达式替换，来编辑行。如果是这样，您将需要识别(J, K)值。一种方法是包含一个哨兵值作为每次更新的一部分，一些在原文中从未出现过的价值。那就简单了要定位它，发出delete_sentinel操作，然后继续。
如果你不能观察编辑操作，所以你只有新旧琴弦，然后事情变得更加困难。Myers描述了一种O(ND)差分算法及其变体来解决这个问题。