如何找到3个或更多字符串的公共部分？

Question

背景（简化）

我有很多文件是由第三方自动生成的（想想多个不同地址合并的输出），我正试图以编程方式从中恢复原始模板和地址/自定义数据。在

我目前所看到的

有很多库（jsdiff，difflib）来区分两个文件。我发现这样做有助于找出%words changed—这是一个很好的指示，如果两个文件来自同一个模板

问题

所以，现在我正处于将相似的文本文件组合在一起的阶段，现在我最好找到一种方法来区分所有这些文件，将相同的文本与不同的文本分开：

Hello [Mr, Mrs] [NameA, NameB, NameC...], we are pleased to (...)

那么，如何在Javascript/Python中找到3个或更多字符串的公共部分呢？在

Answer 1

我想你需要一个后缀树（wikipedia）。 为每个文档构建后缀树。如果你不在乎单个字符，请随意使用单词而不是字符。在

一旦你有了这个，你需要找到从根最长的路径，在所有（或大多数）单独的后缀树。所以只需选择一个，获取所有节点的根并执行DFS，只有在所有（或足够多）树中找到一个链接时，才可以沿着该链接走。这将遍历所有文档中常见的所有子字符串。在

不确定是否有一个lib已经完成了所有这些，但是应该已经有一些东西可以帮助您构建后缀树。在