MEM是「最大精確匹配」問題的縮寫，此問題的目的是查找兩個輸入字符串之間的所有最大相似子字符串。請注意，這個問題與字符串匹配問題（或文本搜索）有點不同，因爲您希望在其他文本中找到給定的字符串。用於MEM查找的高效算法
例如在以下兩個字符串（具有有限charcharchers {1,2,3}）MEM的是 「12」 和 「3312」
STR1： 「12233312」
STR2： 「123312」
例如，233也是兩個輸入字符串之間的常見子字符串，但由於還有另一個包含它的biger子字符串，因此我們不認爲它是MEM。
有沒有人有一些優雅的想法如何解決它。一個非常簡單的想法可以是使用搜索算法來尋找所有可能的小字符串的大字符串，比如Boyer-Moore。但它似乎並不是解決這個問題的有效方法。
是的，你可以做到這一點相對容易，其稱爲動態編程。 
創建一個布爾2D表格，你的第一個維度是你的str1，你的第二個維度是str2。將所有常用數字設置爲true。一旦你完成bollean 2D表格，對角迭代並找到最大的真值。
這個程序的時間複雜度和內存使用量是o（n^2）我需要一些更高效的算法。特別是因爲在我的情況下，一個字符串太長（假設爲1000000個字符），另一個字符串較小。然後，這個表格非常稀疏並且記憶力減弱。如果我決定用鏈接列表的想法來實現它，那麼時間複雜性應該是另一個問題。但到目前爲止，這是最好的主意，謝謝。 – user2373198 2015-02-09 12:40:58
首先。我沒有寫任何'節目'。我只是告訴你如何解決你的問題。其次，在你有人回覆你之後開始添加它們之前，先詳細說明你的所有要求。最後，我建議你閱讀動態編程的工作原理。它的*你的*程序將會提高效率 – Nostradamus 2015-02-09 12:57:45
這是一個線性時間算法。
建設上str1 + "X" + str2，其中'X'不會出現在str1或str2後綴樹。
某些葉節點對應於在str1（包含'X'）開頭的後綴。將這些紅色着色。將其他顏色染成藍色。
步行樹根到葉標籤每個節點的字符串的長度從它的根。
步行樹葉到根以找到同時具有紅色後裔和藍色後裔的葉節點。在步驟3中計算出的標籤是公共子字符串的長度。
我找到了我正在尋找這個問題的紙張。這個想法與大衛艾森斯塔特的一個想法是一致的。實際上，我不需要對兩個字符串進行協調，並且...，我可以構建第一個字符串的後綴樹，然後在previos樹上構建第二個字符串的後綴樹。這意味着當我遍歷前一棵樹來尋找secons字符串的方式時，我可以找到共同的路徑，它顯示了常見的子字符串。
是不是這只是最長的公共子串'問題'？ http://en.wikipedia.org/wiki/Longest_common_substring_problem – leppie 2015-02-09 10:02:27
我不是隻看一個共同的最大子字符串，但也爲所有可能的公共最大子字符串。但也許我可以使用這個想法 – user2373198 2015-02-09 10:07:10
233是*不包括在一個更大的公共子字符串中。 – 2015-02-09 14:13:00