私の友人はこの質問をインタビューで尋ねました。 テキスト文書（ニュース記事など）と一連のキーワード（Google検索用語の場合）を指定した場合、これらのキーワードを含むテキスト文書の中で最も小さいセグメントを（任意の順序で）検索します。k個のキーワードを持つ最小のテキスト断片
私が考えることのできる方法は、キーワードとそのテキスト中のキーワードの位置を含むマップを使用することです。次に、このマップを使用してテキストフラグメントを選択します。しかし、私はより良い方法を探していました。
私はおそらくそのようなものを提案しているだろう：
1. create a new map of <String, Integer> of size k to associate each keyword
with its number of occurences in the text
2. go through the text and each time you encounter a keyword, increment its
number of occurences in the map
3. check that each keyword has been encountered at least once, otherwise
return a proper statement
4. start from the beginning of the text and each time you encounter a keyword,
decrement its number of occurences:
4.1. if the number reaches 0, stop iterating and set
int startIndex = currentIndex
4.2. otherwise keep iterating
5. start from the end of the text and each time you encounter a keyword,
decrement its number of occurences:
5.1. if the number reaches 0, stop iterating and set
int endIndex = currentIndex
5.2 otherwise keep reverse iterating
6. return [startIndex, endIndex]
全体的な複雑さはO（n）があります。
私はニュース記事のすべてのサフィックスを探し、キーワードと比較します。接尾辞木は線形時間で構築することができます。複雑さはO（n log n）です。
各キーワードに関連付けられたカウンタ（map<string,int>など）とキーワードのキューという2つの情報を持つデータ構造が必要です。あなたは文章を辿り、遭遇したキーワードごとにこれを行う：
セット状態=不完全。 カウンタをインクリメントします。すべてのカウンタが0より大きい場合、state = complete（すべてのキーワードがある）を設定します。 テキストの位置とともにキューの背面に挿入します。 キューの前にあるキーワードのカウンタが1より大きい間は、そのキーワードを前面から削除し、カウンタを減らします。 状態が==完了している場合は、キューの先頭にあるキーワードの位置を確認します。それはすべてのキーワードを持つ区間の始まりです。
テキストファイルを1回だけ通過すると、実際にこのタスクを完了することができます。解はO（n + $ \ Sigma k_i $）にあります。$ k_i $はキーワードの長さで、KMP algorithmを大量に使用しています。私は、テキストとキーワードの長さの合計に関して、キーワードの数が少ないと仮定していることを付け加えておきます。
最初のパスの最後に、すべてのキーワードを含む最小のテキスト部分が見つかりました。
最初に、最小長のフラグメントがいずれかのキーワードで始まることがわかります。
2つのハッシュテーブルを維持します。最初のハッシュテーブルには、キーワードとそのカウントが含まれます。 2番目のハッシュテーブルには、それらのキーワードの位置が含まれます。変数に見つかったキーワードの数を格納して、すべてのキーワードが見つかったかどうかを素早く特定できるようにします。変数の中のテキストフラグメントのbegとendを更新します。最後に最小の長さのテキスト断片を維持するために最小カウンタを維持する。
キーワードが最初に出現するまで、入力単語を単語で読み始めます。
このキーワードの位置を2番目のハッシュテーブルに格納します。
最初のハッシュテーブルをチェックインすると、この断片がこの断片に見られるかどうかがチェックされます。
もしそうでなければ、最初のハッシュテーブルでこの単語のカウントをインクリメントし、見られるキーワードの数のカウントを増やします。
これ以外の点は、ハッシュテーブルからこの単語の既存の位置があるかどうかをチェックし、それを とフラグメントの先頭の単語と比較してください。それらが同じ場合は、 ポインタを前方に移動し、別のキーワードを見つけるまで前方に移動し続けます。次に、このキーワードの同じチェックを行います。これがこのキーワードの最新の位置でない場合は、前進してください。最新の位置が先頭のキーワードである場合は、 ポインタを停止します。
表示されたキーワードの数がキーワードの数と等しいかどうかを確認するたびに、すべてのキーワードがチェックされます。はいの場合、終了ポインタと開始ポインタの差を計算し、それに応じて最小長を更新してください。
すべての単語を読み終えたら、最小長を保持する変数はansです。
私はトリックが正しい方法で開始ポインタを移動することだと思います。そのため、2つのハッシュテーブルが必要です。これは線形です。なぜなら、始点のポインタは常に任意の点で前に移動するからです。
私はこれが最小のフラグメントを保証しないと確信しています、* a *フラグメントのみです。 –
あなたはそうです。このアルゴリズムには欠陥があり、保証はありません。私はより良いものを考え出すつもりです:) –