• 締切済み

DPマッチングのプログラミング

Perlで記述されたDPマッチングのプログラムが欲しくて以下のようなサイト http://chalow.net/2007-01-22-4.html でソースを見つけたのですが,その実行結果が別のサイトで見たDPマッチングの説明と食い違うところがあり,本当に正しい実行結果なのかわかりません.実行結果は以下の通りで,同様の結果はWebサイトにも載っています #foosurgerybar と survey を比較 % ./dp.pl _ _ f o o s u r g e r y b a r _ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 s 1 1 1 1 0 1 1 1 1 1 1 1 1 1 u 2 2 2 2 1 0 1 2 2 2 2 2 2 2 r 3 3 3 3 2 1 0 1 2 2 3 3 3 2 v 4 4 4 4 3 2 1 1 2 3 3 4 4 3 e 5 5 5 5 4 3 2 2 1 2 3 4 5 4 y 6 6 6 6 5 4 3 3 2 2 2 3 4 5 具体的な疑問点としては, ・1行目(0が並んだ横行)と1列目(0~6が順番に並んだ縦列)は,一般的なDPマッチングの行列では生成されないのでは? ・スコアが5となっているが,どんなに少なく見積もってもスコアは7以上になるのではないか?(文字列長の差が7だから) です.どなたかよろしくお願いいたします.

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

一番上の行と一番左の列は「プログラムの都合」(例えば「あった方がプログラムが簡単になる」など) で存在してるんだと思います. で, そこでの「スコア」は「先頭や末尾にかたまって存在する『不一致部分』を無視する」ということになっていないかなぁ.

関連するQ&A

専門家に質問してみよう