2

問題：

文字列のリストを指定して、一致するすべての文字列の先頭から減算され、エスケープバイトに置き換えられた場合に、最短の全長を与える部分文字列を見つけます。

例：

"foo"、、"fool"_"bar"

結果は次のようになります。文字列"\0"、、、および全長が9バイトのベース文字列としての「foo」 。エスケープバイトです。元の文字列の長さの合計は10であるため、この場合は1バイトしか保存しませんでした。"\0l""bar""\0"

単純なアルゴリズムは次のようになります。

for string in list
  for i = 1, i < length of string
      calculate total length based on prefix of string[0..i]
      if better than last best, save it
return the best prefix

それで答えはわかりますが、O（（n * m）^ 2）のようなもので、高すぎます。

4

3 に答える 3

7

プレフィックスツリーのフォレストを使用する（トライ）...

  f_2    b_1
 /       |
 o_2     a_1
 |       |
 o_2     r_1
 |
 l_1

(depth * frequency)次に、エスケープ文字に置き換えられるものを最大化することで、最良の結果を見つけて保証することができます。分枝限定法を最初に最大値で検索することにより、検索を最適化できます。

複雑さについて：コメントで述べたように、O（C）は、それを構築し、最適なものを見つけるために、依存します。最初の要素の頻度（O（A）-Aは言語のアルファベットのサイズ）を注文すると、より多くのブランチを切り取ることができ、劣線形時間を取得する可能性が高くなります。

これは明らかだと思います、私はそれを書くつもりはありません-これは宿題とは何ですか？;）

于 2008-09-29T21:19:26.620 に答える
1

さて、最初のステップはリストをソートすることです。次に、リストを1回通過し、各要素を前の要素と比較して、最長の2文字、3文字、4文字などの実行を追跡します。その場合、図は15個の4文字プレフィックスよりも20個の3文字プレフィックスの方が優れています。

于 2008-09-29T21:19:28.227 に答える
1

リストをソートすることから始めてみます。次に、最初の文字を次の文字列の最初の文字と比較して、文字列から文字列に移動するだけです。一致したら、次の文字を確認します。これまでの最良の結果を追跡する方法を考案する必要があります。

于 2008-09-29T21:15:36.550 に答える