php - 查找公共子串

Question

我有N个字符串。我正在寻找至少出现在 2 个字符串中的至少 2 个字符长的所有子字符串。

对于以下字符串：

1. 我的名字是丹尼尔
2. 你叫什么名字？
3. 他们叫我丹尼尔

它应该返回（不包括只有一个字符的字符串）：

• “名称” – 1. & 2.
• “是” – 1. & 2.
• “丹尼尔” – 1. & 3.
• “我” – 1. & 3.
• "y" – 1. & 3.

字符串的长度可能非常长（1KB-10KB）。我几乎没有内存问题（~2GB）——我只需要尽快计算出那些常见的字符串。

提前致谢！丹尼尔。

Answer 1

我发现我最好的选择是在字符串之间进行所有可能的组合（大约 n^2 组合），然后对每个组合运行 LCS 算法。现在我可以比较所有处理它们的结果。

对于 LCS 算法的每次运行，它是 O(n^2*m^2) - n^2 的 O(m^2) 组合。

我知道这是幼稚的实现，但它是我能找到的最好的实现。

不管怎么说，还是要谢谢你 ：-）

Answer 2

我建议在数据库中创建 3 个表：

1. 包含文本中单个单词的索引表
2. 包含文本的表格
3. 包含从单词到文本的引用的表

该方法将是这样的：

1. 将字符串添加到文本表(2)
2. 将字符串拆分为单词
3. 对于每个单词：如果该单词不在索引 (1) 表中，则添加它。
4. 对于每个单词：在参考表中添加一个条目（3），链接到单词和文本表

如果你有这个结构，你现在可以很容易地计算某些单词，它们出现的频率以及它们出现的位置。

如果你把索引放在索引表上的话，你可以搜索得非常快。