2011-01-13 43 views
1

我試圖創建一個腳本,通過查找字符串的文件和報告,對它們之間最常見的子字符串列表。如何比較一組字符串找到共同的子

例如:

  1. 您好,我是一個字符串。我喜歡蘋果和橘子。我們都在這裏。
  2. 你好,我是串二。我喜歡蘋果和橘子。我們都在這裏。
  3. 你好,我串三。我喜歡蘋果和橘子。我們都在這裏。
  4. 你好,我是字符串四。我喜歡蘋果和橘子。我喜歡錶達我的個性。

我想讓腳本告訴我什麼是字符串之間的共同元素,高於某個閾值(例如5個字符)。

理想情況下我會告訴

  • 「我喜歡蘋果和橘子」發生在所有文件
  • 「你好,我是字符串」發生在所有文件
  • 「我們都是這裏的字符串「發生在三個文件中。

如果存在函數來做到這一點的技術,我熟悉 - SQL,Java腳本,PHP,Ruby或猛砸-I'll非常高興......

非常感謝,

傑克

+0

這個問題是密切相關的,並有許多相關答案:http://stackoverflow.com/questions/1410822/how-can-i-detect-common-substrings-in-列表中的字符串 – 2013-06-04 08:00:01

回答

2

這是被稱爲Longest common subsequence problem一個難題。

下面是使用動態編程算法的一個Python實現:http://www.algorithmist.com/index.php/Longest_Common_Subsequence

我不認爲任何標準庫(C,Java,PHP和Python和JavaScript中,紅寶石等),配備了這樣的功能。但是,你可能會尋找實現此:http://www.google.com/codesearch?q=%22longest+common+subsequence%22

+0

啊,謝謝你。現在我知道我設法找到一些預先構建的實現的名稱:http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring#PHP – 2011-01-13 17:30:52