>>342
メモリ消費にある程度融通が利くならSuffixArray（もしくはSuffixTree）を使うといいんじゃまいか？
文字列集合全体に対してSuffixArrayを作り、各インデックスとペアで所属するstringへのポインタなりを格納しておけば
全体で数千万文字あっても20〜30回程度の探索で含まれている部分を見つけることができるはず。