從百萬字的列表中獲取子字符串的計數

Question

我正在嘗試獲取存在於java中的百萬字列表中的子字符串的計數。循環遍歷每個字符串以檢查前一個值是否包含下一個值似乎有一個主要的性能問題。用更少的文字，它可以正常工作，但是當涉及一百萬字的巨大列表時，需要很長的時間才能重新計數。有人能告訴我最快的方法嗎？

Answer 1

我認爲你可以在2N時間得到它。

1. 循環拋出所有列表並將字符串連接成一個或將其逐行放入文件或某物中。你可以得到包含所有單詞的ONE_BIG字符串。如果字符串很大，請使用file並通過unix運行regexp。
2. 循環拋出所有單詞並在您的ONE_BIG上使用正則表達式並將其計數。

這是我的簡單想法。但也許有人有更好的。我好奇地等着。

Answer 2

一個簡單的解決方案是將所有子字符串插入Set，然後檢查集合的大小。

如果這太慢或太耗費內存，自定義數據類型（例如平衡的字符樹可能會更快）。

我猜測一棵有大約1億個子串的樹就可能存儲在32位jvm中。

對於比那更大的數據集，也許散列篩選算法可能能夠進一步爲內存解決方案。

體面的數據庫或數據存儲可用於索引和存儲子字符串。

也有external sort algorithms可以使用幾個文件，並在所有幾乎沒有任何記憶的所有子排序..

其實，如果你使用的是UNIX或Linux，這足以編寫生成所有子程序，通過sort -q和wc管道它，並得到一個答案可能更快，幾乎沒有編碼。但是這不會讓你通過實驗室，我想。