找到兩個字符串匹配的有效方法

Question

我需要找到兩個字符串相同的所有子字符串。我試圖使用後綴樹來查找子字符串，它工作的很快，但太耗費內存（不適合我的任務）。
有沒有其他想法？

Answer 1

Aho-corasick是一個很好的實現，用於匹配任何數量的字符串，並具有最小的性能問題。你嘗試過嗎？

Answer 2

你可以做滑動窗口，雖然這是更少的內存，但更耗時。

最小的子字符串是一個字符（實際上，空單詞是一個，但讓我們把它放在一邊）。

以字符串1的字符1並將該字符的位置保存在字符串2中的某種數據結構中，如地圖或數組。

然後你採取下一個，（字符串1的字符2），並做同樣的事情。

一旦你達到了串1的末尾，你開始了，但這個時候你串1的每兩個字符和送花兒給人提前採取一個字符檢查字符串的所有位置2.

你這樣做只要你的字符串長度與字符串1相等，這意味着你將字符串1和2作爲一個整體進行比較。

請記住：當字符串2長於字符串1，你需要提前整串1串上每2字符一次，因爲串1可能是字符串的一個子2

如果串1大於字符串2，您可以停止檢查，一旦您的子字符串比字符串2更長，那麼所有其他子字符串都將被檢查。理想情況下，你最終會得到一張地圖（最簡單的形式是二維數組），它保存字符串1中每個字符串1的子字符串的位置。

Answer 3

爲什麼你說後綴樹是消耗太多內存？如果執行得當，它僅消耗O（n）內存。