最長公共子串的這種方法是否正確？

我找到了一個算法Longest Common Substring。通常使用dynamic programming，使用尺寸爲mxn的2-D數組完成，其中m和n是所考慮的兩個串的長度。最長公共子串的這種方法是否正確？

我將爲這兩個字符串構造以下矩陣。

M[i][j] = 1 if s1[i]==s2[j] else 0.

例如，如果字符串是：abcxy和pqaabx

矩陣如下所示：

a b c x y 
p 0 0 0 0 0 
q 0 0 0 0 0 
a 1 0 0 0 0 
a 1 0 0 0 0 
b 0 1 0 0 0 
x 0 0 0 1 0

現在，我尋找在1秒的最大連續序列每個對角線在左上方到右下方向。

其中的最大值將是答案。

我可以執行上面的操作，而不明確使用數組。時間複雜度仍然是O(M*N)。所以，不需要記憶。

任何人都可以指出我哪裏錯了嗎？

來源

2014-02-27 nitish712

看起來不錯，我有什麼理由認爲這是不正確的嗎？ –

@PeterdeRivaz如果這是正確的，那麼爲什麼[wikipedia]（http://en.wikipedia.org/wiki/Longest_common_substring_problem）使用一種使用額外內存的算法？另外，我沒有找到任何具有「O（MN）」複雜性並且沒有額外內存的解決方案。 – nitish712

你的方法是正確的。爲證明假設S1和S2的最長公共子串來自S1 [i..j]和S2 [p..q]。這意味着 S1 [i + k] = S2 [p + k]

這些都位於從（i，p）開始的對角線上。

動態編程解決方案做的是同樣的事情，但不是先計算表格，然後通過對角線路徑計算表格，這取決於它的對角線父母加上它們是否匹配。

EDITED

在使用額外的內存維基百科解決您的評論。這只是爲了清楚。原則上，您只需要維基百科解決方案中的兩行矩陣，並將當前最大計數保存在一個變量中。這是正確的，因爲對於矩陣中的任何（i，j）條目，如果s1 [i] = s2 [j（i，j））， ]）

正如您所看到的，當前行元素僅取決於緊靠上一行的元素。

來源

2014-02-27 14:04:33 sukunrt

你的算法是正確的，但標準的DP方法消除了你的第二階段，並使解決方案更簡單。

除了標記布爾值，然後掃描對角線尋找最長的序列，您可以在構建矩陣時計算對角線長度 - 只需要一次通過。

在時間和空間複雜度方面，兩種解決方案都是O（NxM）。如果您使用位矩陣表示，您的解決方案可以節省一些內存，而另一種解決方案可能稍微快一點。

來源

2014-02-27 15:05:17

我其實不想使用矩陣。我強調，同樣的操作也可以在沒有矩陣的情況下完成。我的意思是使用兩個'循環' – nitish712

@ nitish712：實際上你是對的，你可以使用只有恆定的額外空間和O（NxM）時間。但請注意，維基百科頁面並未建議使用什麼數據結構 - 它僅使用表格描述遞歸過程。 –

最長公共子串的這種方法是否正確？

回答

相關問題