1樓：
建議使用 KMP 演算法，如果是找出出現的位置，時間複雜度為 O(「幾十億字串」的總長 + 「某個子串」的長度)。但題主問的是「包含某個子串所有字串」，那這樣的字串就可以有很多個，而且你得輸出字串而不只是位置，那麼複雜度會大很多。最壞情況下，「幾十億字串」中每乙個都是 200 個 a，「某個子串」是乙個 a，那麼你在找出所有出現位置之後，光是輸出就得輸出 1353400 * 「幾十億」個字元。
2. 如何查詢出同時包含某幾個子串的所有字串？
建議使用 AC 自動機。如果你問的是「如何同時查詢出某幾個子串之一在幾十億字串中出現的位置」，那麼 AC 自動機的時間複雜度是 O(「幾十億字串」的總長 + 「某幾個子串」的總長 * 字符集大小) 或 O((「幾十億字串」的總長 + 「某幾個子串」的總長) * log(字符集大小))。但題主問的是「如何查詢出同時包含某幾個子串的所有字串」，在找出匹配位置之後就得再用 two pointer 進行掃瞄，掃瞄過程中維護每個「某幾個子串」之一匹配了幾次，來求出所有符合條件的字串。
可輸出依然是開銷最大的。
3. 題主的問題到底應該如何解決？
由於複雜度瓶頸在輸出答案上，其它部分隨便做就好了。
2樓：A星際穿越
廣義字尾自動機（廣義SAM）（然鵝我不會┑(￣Д ￣)┍
不過我尋思著幾十億字串。。。怕是讀入都要讀半天，所以速度就別想很快了
當然要是不嫌慢kmp（多子串的話就AC自動機也就是樓上的aho corasick）也行
廣義SAM只需要建一次資料結構即可應對多次查詢，但如果修改了母串。。。那就得重建了，單次重建時間複雜度大概O(幾十億*不超過節*字符集大小)，單詞查詢複雜度就很小了，大概O(子串總長度*字符集大小)
kmp及AC自動機是每次查詢都要對子串建一次資料結構，kmp時間複雜度大概是O(幾十億*不超過節*子串個數+子串總長)，而根據題主要求ac自動機可能就不太行了
c語言處理字串， 但不想編譯器給每個，字串後面都加「 0」符號，要自己做的話，要用什麼方式呢？
子謙 首先，C語言中，字串並不是自動加上 0 字元的。說明下字元陣列和字串 字元陣列指的是有若干char型的元素組成的陣列，但是由於常用char型的陣列表達一些含義完整的自然語言，因此常把char型陣列看成乙個整體，為了方便對於這樣乙個整體的操作，在字元陣列初始化的時候，如果使用char str h...
求教乙個字串生成的演算法？
我覺得沒必要考慮高不高效，只要考慮好生成的字串怎麼存就行了，因為你要的是長度為n的所有組合，那麼必然會輸出所有的字串，所以不管啥演算法都不能使時間複雜度降低到輸出所用時間以下。 zanxas 乙個string佔多少記憶體？用char陣列還是string考慮過沒？26 10 36 36的五次方是多少？...
字串搜尋問題，如何找出字串 S 求最長的形式為 x yy 的字首
王天賜 應該不需要擴充套件kmp。直接執行kmp演算法，求出fail函式。對於任意乙個字首，可以根據它的長度和它結尾位置所對應的fail值求出這個字首的最小週期。然後檢查一下該字首的最小週期能不能整除字首長度的一半就好了 實際上是檢查長度的一半是不是乙個週期 z algorithm 和擴充套件kmp...