string - 如何比较一组字符串以找到共同的子字符串

Question

我正在尝试创建一个脚本来查看字符串文件列表并报告它们之间最常见的子字符串。

例如：

1. 你好，我是一弦。我喜欢苹果和橘子。我们在这里都是字符串。
2. 你好，我是二线。我喜欢苹果和橘子。我们在这里都是字符串。
3. 你好，我是三号线。我喜欢苹果和橘子。我们在这里都是字符串。
4. 你好，我是四弦。我喜欢苹果和橘子。我喜欢表达我的个性。

我希望脚本告诉我字符串之间的共同元素是什么，高于某个阈值（例如，5 个字符）。

理想情况下我会被告知

• “我喜欢苹果和橘子”出现在所有文件中
• “你好，我是字符串”出现在所有文件中
• “We are all strings here”出现在三个文件中。

如果在我熟悉的技术（SQL、Javascript、PHP、Ruby 或 Bash）中存在执行此操作的函数，我会非常高兴...

非常感谢，

杰克

Answer 1

这是一个被称为最长公共子序列问题的难题。

这是使用动态编程的算法的 Python 实现：http ://www.algorithmist.com/index.php/Longest_Common_Subsequence

我不认为任何标准库（C、Java、PHP、Python、Javascript、Ruby 等）都带有这样的功能。但是您可以在这里寻找实现：http ://www.google.com/codesearch?q=%22longest+common+subsequence%22