0
我正在尋找將從文件中提取所有常見模式的算法，原始算法需要O（n^2）。要找出所有常見模式，我需要生成所有子字符串並在另一個給定文件中檢查它。我正在尋找一些數據結構或算法，以便不需要生成所有子字符串。對於相同的字符，是否有任何有效和優雅的算法。從兩個文件中有效地找到所有常見模式（子串）
爲了簡單起見，我們將文件視爲字符串。假設我們必須字符串str1 =「xxabcyy」和str2 =「sydabcdy」，所以預期輸出是{「abc」，「y」}。例如我有所有可能的子字符串str1即{「x」，「xx」，「xxa」，「xxab」，「xxabc」，「xxabcy」，「xxabcyy 「，」xa「，」xab「，..}然後檢查每個子字符串是否在str2中。
反正卡普 - 拉賓可以做同樣的事情爲O更好（| S | + | T |） – Roylee
@Roylee我知道karp-rabin有O（| s | + | t |），但在我的情況下，問題在於找出我需要爲所有子字符串生成的通用模式，並與另一個給定文件匹配，模式匹配更晚階段。我正在尋找一些數據結構或算法，以便我不需要生成所有子字符串。 –
「要找出我需要爲所有子字符串生成的常見模式」，我不太明白這一點，或許您想要重新修改它:) – Roylee