2

SPOJ でこの問題を解決しようとしています: http://www.spoj.pl/problems/EDIT/

アルゴリズムの適切な再帰的な説明を取得しようとしていますが、私の考えがぐるぐる回っているので失敗しています! これで私を助けてもらえますか？これを解決しようとしているアプローチを説明しようと思います。

基本的に、i が開始インデックス、j が終了インデックスであるサイズ ji の問題を解決したいと考えています。ここで、2 つのケースがあるはずです。ji が偶数の場合、開始文字と終了文字の両方が同じである必要があり、ji が奇数の場合は逆である必要があります。小さいサイズの問題 (ji-1 または ji-2) も削減したいのですが、小さい問題の解決策を知っている場合は、より大きな問題の解決策を構築する際にも、より小さな問題の開始と終了のレターケース。これはまさに私が混乱しているところです。私の考えを正しい軌道に乗せることができますか？

4

3 に答える 3

3

再帰は、この問題を解決する最善の方法ではないと思います。別のアプローチを取ると、非常に迅速に解決できます。

バイナリ文字列を考えてみましょう。大文字の char が1で、小文字のchar が0だとします。例えば

AaAaB -> 10101
ABaa  -> 1100
a     -> 0

「正しい」交互チェーンは10101010 .. または010101010 ..

ある文字列を別の文字列に変更するために必要な置換の最小数を、文字列間のハミング距離と呼びます。見つけなければならないのは、入力バイナリ文字列と同じ長さの 2 つの交互チェーンの 1 つとの間の最小ハミング距離です。

難しいことではありません。各文字列を XOR し、1 の数を数えます。（リンク）。たとえば、次の文字列を考えてみましょう: ABaa .

  • これをバイナリに変換します。

    アバア -> 1100

  • 長さ 4 の 2 つの交互チェーンのみを生成します。

    1010

    0101

  • それらを入力と XOR します。

    1100 XOR 1010 = 0101

    1100 XOR 0101 = 1010

  • 結果の 1 をカウントし、最小値を取ります。この場合、それは2です。

この手順を Java でコーディングし、いくつかのマイナーな最適化 (バッファリングされた I/O、代替チェーンを生成する必要はありません) を行ったところ、受け入れられました: (0.60 秒 1)。

ここに画像の説明を入力

于 2012-09-16T13:40:46.530 に答える
1

長さnの任意の文字列が与えられた場合、可能な「交互チェーン」は2つだけです。この2つのバリアントは、最初の文字の状態を設定することで順番に定義できます（1番目が上、2番目が下、3番目が上...）。

単純な線形アルゴリズムは、最初の文字について2つの単純な仮定を行うことです。

  1. 最初の文字は大文字です
  2. 最初の文字は小文字です

仮定ごとに、簡単な距離編集アルゴリズムを実行すれば完了です。

于 2012-09-16T10:51:48.137 に答える
1

再帰的に実行できますが、関数間で多くの状態情報をやり取りする必要があります。この問題が単純なループで解決できる場合、これは価値がないと思います。

他の人が言うように、2 つの「望ましい結果」文字列が考えられます。1 つは大文字で始まり (result_U と呼びましょう)、もう 1 つは小文字で始まります (result_L)。EditDistance(input, result_U) と EditDistance(input, result_L) の小さい方が必要です。

また、EditDistance(input, result_U) を計算するために、result_U を生成する必要はなく、入力を一度に 1 文字ずつスキャンするだけでよいことに注意してください。想定されたケースではない各文字は、それをつまり、編集距離に 1 を追加します。EditDistance(input, result_L) についても同様です。

また、2 つのループを組み合わせて、入力を 1 回だけスキャンすることもできます。実際、これは各入力文字列の読み取り中に実行できます。単純なアプローチは次のようになります。

擬似コード:

EditDistance_U = 0
EditDistance_L = 0

Read a character
To arrive at result_U, does this character need editing?
  Yes => EditDistance_U += 1
  No  => Do nothing
To arrive at result_L, does this character need editing?
  Yes => EditDistance_L += 1
  No  => Do nothing
Loop until end of string
EditDistance = min(EditDistance_U, EditDistance_L)

上記にも実行できる明らかな最適化がありますが、それはあなたに任せます。

ヒント 1: ループに 2 つの条件が必要ですか? それらは互いにどのように関連していますか？

ヒント 2: EditDistance_U + EditDistance_L とは?

于 2012-09-16T15:17:53.823 に答える