文字列中の単語の集合から単語が出現する

Question

誰かが文字列中のK単語の集合から任意の単語の出現を見つけるアルゴリズムを提案できますか？例について
：単語の
セット：{ABC、XYZ}
文字列：ABC defghi内ABC jklab XYZ
出力：{0,9,17} //内の単語の開始位置文字列

KMPを実行するよりも何か良い時間！

Answer 1

Aho-Corasick algorithmは、テキスト内の特定の辞書から任意の単語を検索することを目的としています。

は、このタスクのためにsome other algorithmsがあります - Commentzヴァルター、ラビン - カープ

Answer 2

産業規模でこれを行う場合は、接尾辞ツリーを使用します。文字列にすべてのサフィックスを格納すると、すべてのサブ文字列が異なるサフィックスを持つ同じ文字列であるため、実質的に一定の時間内にサブ文字列を検索できます。

しかし、サフィックスツリーが複雑さを正当化する前に文字列を非常に長くする必要があります（実際にはDNA配列データをスキャンするために使用されます）。