0

文字列のセットが与えられた場合、

ap***
ab*le
a****
ab***

問題は、文字列の数と許容される差異の数を考慮して、文字列のセットが一貫しているかどうかを見つけることです。

したがって、上記のセットでは、単一の矛盾する文字列（2番目の文字列）を許可する場合、答えは「はい」ですが、矛盾する文字列を許可しない場合は「いいえ」です。

最良のアルゴリズムは何ですか、そして複雑さは何ですか？

私が思いついたすべての解決策は、すべての組み合わせを調べる必要があるか、単に間違っています。たとえば、文字列を調べてセットに追加することはできません（「互換性がない」と区別することを定義します）。**、abadが渡されるためです。

実際の問題（から）：問題M

2417年、考古学者は、歴史的に非常に重要な20世紀のテキスト文書の大規模なコレクションを発見しました。重複した文書がたくさんありましたが、テキストの多くを判読できなくする時間による損傷だけでなく、それらの間にもいくつかの不一致があることがすぐに明らかになりました。ただし、テキストのグループを一貫性のあるものにすることができることに気づきました。つまり、テキスト間の一貫性は、いくつかの（少数の）テキストを除外することによって達成できます。たとえば、テキスト：

ap***
ab*le
app*e
*p\**e

（*は判読できない文字を示します）2番目のテキストだけを削除することで一貫性を保つことができます。

入力は、一連のテキストで構成されます。各セットは、セット内のテキストの数と、削除できるテキストの最大数を指定する行で始まります。この後に、1行に1つずつ個別のテキストが続きます。各テキストは、小文字またはアスタリスクのいずれかで、少なくとも1文字から250文字以下で構成されます。セット内のすべてのテキストは同じ長さになり、セット内のテキストは10,000個以下になります。セットのシーケンスは、2つのゼロ（0 0）を含む行で終了します。

各セットの出力は、最大で指定された数のテキストを削除することでセットの一貫性を保つことができるかどうかに応じて、「はい」または「いいえ」のいずれかの単語を含む行で構成されます。

Sample input
4 1
ap***
ab*le
app*e
*pple
3 1
a
b
c
4 2
fred
ferd
derf
frd*
0 0

Sample output
Yes
No
No
4

2 に答える 2

1

これは宿題のように感じるので、いくつかの詳細を省略します。

トライはこれをかなりうまく処理できます。特定のテキストにが含まれているインデックスでは、*そのテキストをトライ内の他のすべての葉から派生させます。次に、トライを歩き、十分なテキストに一致するターミナルノードを探します。

トライには最大でn * mノードがあるため、別のテキストを追加するのはO(nm)です。

トライの構築にも複雑さがあります。正しい順序でテキストを追加する必要があり、各テキストインデックスの正しい順序を確認する必要があります。*bそうしないと、のターミナルノードにが含まれていない状況になってしまう可能性がありますab。しかし、それを行っても、アルゴリズムがさらに複雑になることはありません。

合計時間はO(mn^2)です。構築されたトライを歩くことはO(nm)であり、ノードを追加することはノードO(nm)のためnです。

于 2012-08-15T13:08:43.207 に答える
0

文字列とカウントを使用して、一貫性のある文字列のセットを表すことをお勧めします。文字列には、セット内の文字列のいずれかが文字を持っている位置に文字があり、それ以外の場合はアスタリスクがあります。カウントは、セット内の文字列の数です。したがって、{ab **、a * b *} = [abb *、2]です。

単一の表現[ **、0]から始めます。

文字列Xが表示されるたびに：

1）表現のセットに[X、1]を追加します

2）これまでの表現のいずれかと一致している場合は、文字列と表現から新しい表現を作成します-カウントを増やし、必要に応じて文字列内の文字をさらに修正します。新しい表現を表現のセットに追加します。

3）同じ文字列を持つ表現が複数ある場合は、1つだけを保持し、その文字列を持つ表現の最大数をカウントします。

4）カウントが、これまでに表示された文字列の数から除外できる文字列の数を引いた数より少ない表現を削除します。

5）-次の文字列で（1）から繰り返します

最後に、最も妥当な答えは、もしあれば、最大の数を持つものです。一貫した回答が作成されます。一度に手元にある表現の最大数は、その段階で可能な回答の最大数です。これは、Choose（n、x）です。ここで、Nはその時点で見られる文字列の数であり、xはテキストの数です。破棄することができます。x = 1の場合、これはn（n-1）/2です。これをn回実行する必要があり、他のコストは文字列の長さによってのみ増加するため、O（mn ^ 3）アルゴリズムがあると思います。

于 2012-08-15T04:47:20.370 に答える