找出两段字符串之间的差异，并能找出哪部分是新增的，哪部分是删除的

Question

如下图所示，这是一个文章批改功能。

比如其中有一句“虽然我们相识了10年，我的收入不高”
而批改的话句话是“虽然我们相识了10年，但是因为我的收入不高”
他就能知道“但是因为”是新增的部分，所以标蓝了

再比如其中有一句“反正她最近升职了”
批改的话是“反而是她最近升职了”
他就知道把“正”去掉，新增了“而是”

so，这个功能应该如何实现？只谈谈思路也可，有代码或demo更佳。

Answer 1

可以用git diff的算法, 具体名字叫 Myers 算法

Answer 2

简单的 diff 效果的话可以用 diffjs 这个库，效果还不错，如果涉及到语境分析，那就不太可能了。

Answer 3

接口仔表示：nacos就有这个功能

Answer 4

我突然有一个想法。将两段文字按照某种规则排序，选取教小那段文字，进行二分查找，查找什么呢？查找和长段文字不同的最后一个字符，相同向右，不同向左，直到最后一个。找到这个字符后就好处理了。源右边是被删除了的，处理后的是新增的。只是这样是无序的，如果需要有序，之前加一个索引，之后在按照索引排序即可。

Answer 5

这个其实diff就可以实现，可以把源文件和后面的文件按每个字符分行（原来的分行变成连续2个分行），这样diff直接就可以给出那些是删除的，那些是处理后新增的。

这样把连续删除的接一起，连续新增的接一起就可以给出结果。