如何标记两个字符串之间的差异

doe*_*man 2 string algorithm

我想要一个能够直观地标记两个字符串之间差异的函数。

示例1:

输入:

  • 堆栈溢出
  • 堆栈溢出

输出:

  • 堆栈溢出
  • 堆栈[o]溢出[​​ing]

示例2:

输入:

  • 重新堆叠溢出
  • 堆栈溢出

输出:

  • [Res]大头钉[ ]溢出
  • [S]tack[-]O[ooo]溢出

我已经搜索了很多,但最终总是得到文件比较函数。我想可视化字符串之间的差异。我发现的一个例子是https://text-compare.com(这正是我需要的),但它似乎使用服务器端代码。

语言并不重要,JavaScript、Python,但任何如何解决这个问题的指示都会很好。

我不一定是在寻找实现;我宁愿有一些网站的链接,因为这不是一个基本问题。也不太难,但你想把它做好。

kay*_*ya3 5

这个问题可以通过找到两个字符串的最长公共子序列(LCS),然后仅将不属于 LCS 的部分放在方括号中来解决。

例如,Stack Overflow和的 LCSStack ooverflowing是Stack verflow,因此第一个字符串将呈现为,Stack [O]verflow第二个字符串将呈现为Stack [oo]verflow[ing],因为这些是 LCS 中不存在的部分。

维基百科上描述了一种用于计算 LCS 的标准动态编程算法,并且对该算法进行了各种优化,从而在实际情况下加快了计算速度。每个字符串中不存在于 LCS 中的部分可以通过维护字符串中当前索引和 LCS 中当前位置的另一个索引的简单循环来找到。