4

それぞれ長さkのn個の単語を考えてみましょう。これらの単語は、定義された順序のアルファベット（カーディナリティはn）上の文字で構成されます。タスクは、O（nk）アルゴリズムを導出して、1つの位置が異なる単語のペアの数をカウントすることです（正確にどちらでも、単一の位置である限り）。

たとえば、次の一連の単語（n = 5、k = 4）では次のようになります。

abcd、abdd、adcb、adcd、aecd

そのようなペアは5つあります：（abcd、abdd）、（abcd、adcd）、（abcd、aecd）、（adcb、adcd）、（adcd、aecd）。

これまでのところ、少し簡単な問題を解決するアルゴリズムを見つけることができました。1つの与えられた位置（i番目）だけ異なる単語のペアの数を数えることです。これを行うには、i番目の位置の文字を各単語内の最後の文字と交換し、基数ソートを実行し（各単語の最後の位置を無視します-以前はi番目の位置）、最初の1からk-1の位置は同じであり、最終的には、複製の各セット内の最後の（元々はi番目の）位置での各文字の出現回数をカウントし、目的のペアを計算します（最後の部分は単純です）。

ただし、上記のアルゴリズムは、（O（nk）制約の下で）主な問題には適用できないようです-少なくともいくつかの変更がない場合はそうではありません。これを解決する方法はありますか？

4

5 に答える 5

1

n と k が大きすぎないため、これがメモリに収まると仮定します。

最初の文字が削除されたセット、2 番目の文字が削除されたセット、3 番目の文字が削除されたセットなどを用意します。技術的には、これは文字列からカウントへのマップである必要があります。

リストを実行し、現在の要素を各マップに追加するだけです (明らかに該当する文字を最初に削除します) (既に存在する場合は、count を totalPairs に追加し、1 ずつ増やします)。

次に、totalPairs が目的の値です。

編集：

複雑：

これはする必要がありますO(n.k.logn)。

HashMap理論的な複雑さのために、ソートされたマップの代わりに、ハッシュを使用するマップ (Java など) を使用できますO(nk)(ただし、一般に、ハッシュ マップはソートされたツリーベースのマップよりも遅いことがわかっています)。

改善：

これに対する小さな変更は、最初の 2 文字を削除して 2 つのマップにすることです。1 つは最初の文字を削除し、もう 1 つは 2 番目の文字を削除し、3 番目と 4 番目の文字も同様にします。

次に、これらを 4 文字を削除してマップに配置し、それらを 8 文字を削除してマップに配置し、最大で半分の文字を削除します。

これの複雑さは次のとおりです。

  • 最大 k 個の要素を含む 2 つの並べ替えられたセットに 2 つのルックアップを行います (各半分について)。

  • これらのそれぞれについて、(四半期ごとに) 2 つのソートされたセットへの 2 つのルックアップを再度実行します。

  • したがって、ルックアップの数は 2 + 4 + 8 + ... + k/2 + k であり、これはO(k).

  • ここで間違っているかもしれませんが、最悪の場合、特定のマップの要素数は ですn。しかし、これにより、他のすべてのマップは 1 つの要素しか持たO(logn)なくnなりn.kます。

だから私はそれだと思いますO(n.(logn + k))。

.

編集2：

私のマップの例（改善なし）：

(x-1)xはにマップすることを意味します1。

あるとしましょうabcd, abdd, adcb, adcd, aecd。

最初のマップは(bcd-1), (bdd-1), (dcb-1), (dcd-1), (ecd-1).

2 番目のマップは次のようになります(acd-3), (add-1), (acb-1)(4 番目と 5 番目の値は既に存在するため、インクリメントします)。

3 番目のマップ : (abd-2), (adb-1), (add-1), (aed-1)(2 番目は既に存在します)。

4 番目のマップ : (abc-1), (abd-1), (adc-2), (aec-1)(4 番目は既に存在します)。

totalPairs = 0

2 番目のマップには - acd、4 番目には 1 を追加し、5 番目には 2 を追加します。

totalPairs = 3

3 番目のマップについては - abd、2 番目については 1 を追加します。

totalPairs = 4

4 番目のマップについては - adc、4 番目については 1 を追加します。

totalPairs = 5.

改善されたマップの部分的な例:

上記と同じ入力。

最初の 2 文字のマップが削除され、1 番目と 2 番目の文字のマップが削除されました:

(cd-{  {(bcd-1)}, {(acd-1)}  }),
(dd-{  {(bdd-1)}, {(add-1)}  }),
(cb-{  {(dcb-1)}, {(acb-1)}  }),
(cd-{  {(dcd-1)}, {(acd-1)}  }),
(cd-{  {(ecd-1)}, {(acd-1)}  })

上記は、cd1 つの要素(bcd-1)を含むマップと を含むマップの 2 つのマップにマップされた要素で構成されるマップ(acd-1)です。

ただし、4 番目と 5 番目はcd既に存在するため、上記を生成するのではなく、次のようにそのマップに追加されます。

(cd-{  {(bcd-1, dcd-1, ecd-1)}, {(acd-3)}  }),
(dd-{  {(bdd-1)}, {(add-1)}  }),
(cb-{  {(dcb-1)}, {(acb-1)}  })
于 2013-01-04T20:15:04.393 に答える
0

各単語を配列に入れることができます。その配列から要素を1つずつ取り出し、結果の配列を比較します。最後に、ポップされた要素を追加して元の配列に戻します。両方の配列からポップされた要素は同じであってはなりません。これが発生したケースの数を数え、最後に2で割って、正確な解を求めます。

于 2012-11-07T04:57:17.207 に答える
0

ここに問題を提出してから 2 か月が経ちました。その間、同僚と話し合い、その結果を共有したいと思います。

主なアイデアは、Dukeling によって提示されたものと似ています。各単語 A とその単語内の各 i 番目の位置について、タプルを検討します: (接頭辞、接尾辞、i 番目の位置の文字)、つまり (A[1..i-1]、A[i+1. .n]、A[i])。i が 1 または n の場合、該当する部分文字列は空と見なされます (これらは単純な境界ケースです)。

これらのタプルがあれば、最初の投稿で説明した推論を適用して、異なる単語のペアの数を数えることができるはずです。タプルを接頭辞と接尾辞の値で (i ごとに個別に) ソートするだけで済みます。その後、文字がまったく同じで i 番目の位置が互いに隣接する単語が表示されます。

ここに私が欠けている技術的な部分があります。並べ替え手順 (RadixSort が適しているようです) を O(nk) 制約を満たすようにするために、接頭辞と接尾辞にラベルを割り当てたいと思うかもしれません (i ごとに n 個のラベルしか必要ありません)。ラベル付けの方法についてはよくわかりません。(もちろん、代わりにハッシュ化を行うこともできますが、前者のソリューションが実行可能であると確信しています)。

これは完全な解決策ではありませんが、この問題に取り組む可能性のある方法に光を当てると信じており、それが私がここに投稿した理由です. 誰かがラベル付けの部分を行う方法のアイデアを思いついたら、この投稿でそれを実装します.

于 2013-01-11T19:59:24.253 に答える