回覆列表
  • 1 # 使用者3294091990964

    如何從幾十億字串(每個字串不超過200位元組)中,查找出,包含某個子串所有字串?

    建議使用 KMP 演算法,如果是找出出現的位置,時間複雜度為 O(“幾十億字串”的總長 + “某個子串”的長度)。但題主問的是“包含某個子串所有字串”,那這樣的字串就可以有很多個,而且你得輸出字串而不只是位置,那麼複雜度會大很多。最壞情況下,“幾十億字串”中每一個都是 200 個 a,“某個子串”是 一個 a,那麼你在找出所有出現位置之後,光是輸出就得輸出 1353400 * “幾十億”個字元。

    2. 如何查找出同時包含某幾個子串的所有字串?

    建議使用 AC 自動機。如果你問的是“如何同時查找出某幾個子串之一在幾十億字串中出現的位置”,那麼 AC 自動機的時間複雜度是 O(“幾十億字串”的總長 + “某幾個子串”的總長 * 字符集大小) 或 O((“幾十億字串”的總長 + “某幾個子串”的總長) * log(字符集大小))。但題主問的是“如何查找出同時包含某幾個子串的所有字串”,在找出匹配位置之後就得再用 two pointer 進行掃描,掃描過程中維護每個“某幾個子串”之一匹配了幾次,來求出所有符合條件的字串。可輸出依然是開銷最大的。

    3. 題主的問題到底應該如何解決?

    由於複雜度瓶頸在輸出答案上,其它部分隨便做就好了。

  • 中秋節和大豐收的關聯?
  • 求帶有“夢”和“傑”的成語或詩句(我想起個帶有這兩個字的好聽網名),諧音當然也可以?