3

'n' 個の文字列 w1、w2、......、wn が与えられます。文字列 wi のすべての一意の部分文字列を考慮することによって形成される文字列のセットを Si とします。部分文字列は、文字列内の 1 つ以上の文字の連続シーケンスとして定義されます。部分文字列の詳細については、こちらを参照してください。'S' = {S1 U S2 U .... Sn} とします。つまり、'S' は、すべてのセット S1、S2、..... Sn 内のすべての一意の文字列を考慮することによって形成される文字列のセットです。多くのクエリが与えられ、クエリごとに整数「k」が与えられます。あなたの仕事は、セット 'S' から辞書編集的に k 番目に小さい文字列を出力することです。

入力：

入力の最初の行には、文字列の数を示す単一の整数「n」が含まれています。次の「n」行はそれぞれ文字列で構成されます。i 行目 (1<=i<=n) の文字列は wi で示され、長さは mi です。次の行は、クエリの数を示す単一の整数 'q' で構成されます。次の「q」行はそれぞれ、単一の整数「k」で構成されます。

注: 入力文字列は、小文字の英字 'a' から 'z' のみで構成されます。

出力：

'q' 行を出力します。ここで、i 行目は、i 番目のクエリに対する回答である文字列で構成されます。入力が無効な場合 ('k' > |S|)、その場合は "INVALID" (わかりやすくするために引用符) を出力します。

制約:

1<=n<=50
1<=mi<=2000
1<=q<=500
1<=k<=1000000000

https://www.interviewstreet.com/challenges/dashboard/#problem/4efa210eb70ac

私のアプローチ

入力文字列ごとに、その部分文字列を生成してセットに追加します。これにより、重複が自動的に排除され、ソートされた状態が維持されます。セット内のインデックス i の要素を返します。

上記のアプローチでコードをここに書きました：

http://justprogrammng.blogspot.com/2012/06/interviewstreet-find-strings-solution-c.html

しかし、私が直面している問題は

terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Aborted (core dumped)

このエラーは、いくつかのテスト ケースで発生しています。このエラーが発生する理由と、このエラーを修正する方法を教えてください。

4

3 に答える 3

3

@enjayの答えは正しいです。この種の文字列処理アルゴリズムの問​​題に不慣れで、さらに学びたい人のために詳しく説明します。私の答えは、全体像を示し、言及された詳細へのポインタを提供します。

Interviewstreet.com で @sachin が指摘した問題は、部分文字列、回文などが関与する問題の大きなグループに属しています。このような問題はすべて、接尾辞配列 (en.wikipedia.org/wiki/Suffix_array) という 1 つの専用データ構造によって解決できます。完全なラーニング パスは次のとおりです。しかし、問題を解決することのみを求められている場合は、直接 3 に進むことができます。

  1. トライ(http://en.wikipedia.org/wiki/Trie)。サフィックスツリーの基礎。

  2. サフィックス ツリー (http://en.wikipedia.org/wiki/Suffix_tree)。1 つの文字列のすべてのサフィックスをトライに入れます。指定された文字列の部分文字列は、指定された文字列のサフィックスのいずれかのプレフィックスであることに注意してください。サフィックス ツリーのアイデアは刺激的ですが、サフィックス ツリーの構築は複雑すぎて実装できないか、遅すぎるため、実際には誰も使用しないと思います。ただし、誰もが不必要な困難に挑戦したい場合は、サフィックスツリーの構築アルゴリズムの最良の例を次に示します: http://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english

  3. サフィックス配列(http://en.wikipedia.org/wiki/Suffix_array)。サフィックス配列には、サフィックスツリーが持つ情報が含まれており（したがって、サフィックスツリーが実行できることは何でも実行できます）、実装がはるかに簡単です。そうは言っても、それで重要なことを達成したい場合は、RMQ 用に少なくとも 3 つの配列と 1 つのインデックスを構築する必要があります。3 つの配列は次のとおりです。

を。サフィックス配列自体。

b. ランク配列。

c. 高さの配列。

接尾辞配列を使用する場合の一般的なタスクの 1 つは、2 つの接尾辞の最も長い共通の接頭辞を見つけることであるため、高さ配列に対して RMQ クエリを実行する必要があります。RMQ については、http: //en.wikipedia.org/wiki/Range_Minimum_Queryで説明されています。

于 2013-01-13T02:49:01.720 に答える
2

一意のサブ文字列が多すぎてメモリに収まらないため、bad_allocエラーが発生します。これを修正するには、すべての一意の部分文字列を格納する必要がない任意のアプローチを使用できます。

私のソリューションはかなり複雑なので、アルゴリズムのスケッチだけを提供します。

w1、w2、......、wnのすべての可能な位置で始まり、w1、w2、......、wnの終わりで終わる部分文字列のみを格納できます。また、部分文字列全体の代わりに、開始文字へのポインタのみを格納できます。

クエリに答えるために、すべてのクエリを並べ替え、すべてのサブ文字列を並べ替えることができます。次に、次の方法で部分文字列を繰り返します。同じ文字から始まるすべての部分文字列を取得し、次に同じ2番目の文字を持つすべての部分文字列を取得します。つまり、このノードに対応する、残りの一意のサブストリングの長さに等しい重みを持つすべての内部ノードと重みを持つすべてのリーフノードでトライを暗黙的に構築します。そして、この試行を繰り返し、各ノードの重みの累積合計を計算し、それを次のまだ処理されていないクエリと比較します。一致するものが見つかるとすぐに、部分文字列を出力して、トライトラバーサルを続行します。

これはすべて多くのメモリを必要としませんが、計算リソースに非常に飢えています。しかし、それは最適化されるかもしれません。明示的なトライを使用して、すべての短い部分文字列（おそらく、長さが1..2または1..3）を格納できます。また、バケットソートアルゴリズムを使用して、より長いサブストリングをソートすることもできます。

于 2012-06-29T15:48:47.170 に答える
2

接尾辞配列を使用する...すべての部分文字列を生成するよりもメモリ上で高速かつ簡単になります...接尾辞配列を並べ替えてから、lcp配列や累積サブ文字列カウント配列uなどの拡張データ構造を使用して検索してみてください時間内に、メモリの制約内でそれを解決します。

于 2012-08-10T14:11:38.347 に答える