私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「文字列の違いを評価しよう」（CodeIQ）を参照してください。
あなたはとあるデータベースの管理者で、データにスペルミスが含まれる問題を解決したいと考えていました。
しかしデータ量は膨大であり、ひとつひとつ目で確認するのは現実的ではなかったため、まず「編集距離」と呼ばれる"2つの文字列が相違している度合い"を用いて、状況を可視化することにしました。
ただし、本設問で用いる編集距離は、より実用性を高めるため、独自のカスタマイズが加えられています。
求められるプログラムの前提条件は、以下の通りとなります。
標準入力から、制御文字を除くASCII文字のみで構成された2つの文字列が、改行区切りで送られる
各々の文字列は、2文字以上32文字以下とする
英字は大文字、小文字を区別するものとする
標準出力に、以下に定義する編集距離を用いて、文字列の相違を数値として出力する
編集距離は、よく知られるレーベンシュタイン距離（Wikipediaへのリンク）を拡張したものを用います。
文字の挿入、削除、置換といった操作により、一方の文字列をもう一方の文字列に変形するのに必要な手順の組み合わせのうち合計が最小となる距離を、編集距離と定義する点に変わりはありません。
が、以下の表に示す通り、操作と距離のバリエーションが異なります。
※変形例において、変形前と変形後の相違をアンダーラインで示しています
操作 編集距離 変形例 1文字の置換（小文字大文字変換のみ） 1 CodeiQ→CodeIQ 1文字の置換（上記以外） 2 CodeIT→CodeIQ 1文字の挿入 2 CodeQ→CodeIQ 1文字の削除 2 CodeIHQ→CodeIQ 隣り合う文字の転置 2 CodeQI→CodeIQ
以下、出力例になります。
例えば、"abcDe"から"abdce"の場合、abcDe→abDce(+2)→abdce(+1)で距離の合計が最小となるため、編集距離として"3"を出力するのが正しいことになります。
【入出力サンプル】
標準入力1
abcde
abcdE
標準出力1
1
標準入力2
abcdY
abcde
標準出力2
2
標準入力3
abcd
abcde
標準出力3
2
標準入力4
abcde
abde
標準出力4
2
標準入力5
abdce
abcde
標準出力5
2
標準入力6
abcDe
abdce
標準出力5
3
現実のデータベース化の業務において、タイポや表記ゆれのために泣く泣くデータを修正…といったことは意外と多いものです。
そんなとき、編集距離の存在を知っている、さらにニーズに即して拡張することができれば、非常に強力な武器となるでしょう。
是非挑戦してみてくださいね。
【問題】
標準入力から、２つの文字列が送られます。
この２つの文字列の違いを、設問で用意された独自の編集距離を用いて数値化し、その結果を標準出力に返してください。
Rubyで解答しています。
#!/usr/bin/ruby
def solve(a, b)
return 0 if (a.size == 0) && (b.size == 0)
return b.size if a.size == 0
return a.size if b.size == 0
matrix = Array.new(a.size+1){Array.new(b.size+1)}
0.upto(a.size){|i| matrix[i][0] = 2*i}
0.upto(b.size){|j| matrix[0][j] = 2*j}
for i in 1...a.size
for j in 1...b.size
type = [matrix[i-1][j]+2, matrix[i][j-1]+2] # 追加、削除
if a[i-1] == b[j-1] then type << matrix[i-1][j-1]
else
if a[i-1].upcase == b[j-1].upcase then # 大文字、小文字の変換
type << matrix[i-1][j-1] + 1
else
if (a[i-1].upcase == b[j].upcase) && (a[i].upcase == b[j-1].upcase) then # 入れ替え前
if a[i-1] == b[j] then type << matrix[i-1][j-1] + 1
else type << matrix[i-1][j-1] + 2
end
elsif (a[i-1].upcase == b[j-2].upcase) && (a[i-2].upcase == b[j-1].upcase) then # 入れ替え後
if a[i-1] == b[j-2] then type << matrix[i-1][j-1] + 1
else type << matrix[i-1][j-1] + 2
end
else
type << matrix[i-1][j-1] + 2
end
end
end
matrix[i][j] = type.min
end
end
return matrix[a.length-1][b.length-1]
end
# main
input = []
while line = gets
line.chomp!
if line.empty? then next end
input << line + "\n" # 末尾に必ず同じになる文字（改行）をつける
end
p solve(input[0], input[1])
基本的なロジックはWikipediaの記事に疑似コードがあるので、それを使用する言語で実装すれば良いだけです。
問題の仕様で1点面倒なのが入れ替えです。更に、入出力例6を見ると入れ替えと大文字小文字の変換の組み合わせがあり得ることがわかります。この部分をどうするかがポイントです。
function LevenshteinDistance (Character str1 [1 to lenStr1], Character str2 [1 to lenStr2]) return Integer is
begin
(* lenStr1+1 行 lenStr2+1 列のテーブル d を用意する *)
variable Integer d [0 to lenStr1, 0 to lenStr2] ;
for Integer i1 := 0 to lenStr1 do let d[i1,0] := i1 ;
for Integer i2 := 0 to lenStr2 do let d[0,i2] := i2 ;
for Integer i1 := 1 to lenStr1 do
for Integer i2 := 1 to lenStr2 do
begin
constant Integer cost := if str1[i1] == str2[i2] then 0 else 1 ;
let d[i1,i2] := minimum
(
d [i1-1, i2 ] + 1, (* 文字の挿入 *)
d [i1 , i2-1] + 1, (* 文字の削除 *)
d [i1-1, i2-1] + cost (* 文字の置換 *)
)
end ;
return d [lenStr1, lenStr2]
end
入力値をsolve()関数に渡した結果を印字します。
入力値は入れ替えに対応するため末尾に改行文字を付加しています。これは入れ替えを判断するために1文字先読みしなければならないのですがこの時領域違反を起こさないようにするためです。わざわざString#chomp()で改行文字を取ってから付け直しているのは2行目の入力に改行が含まれているかどうかわからなかったので必ず一致するようにこうしました。
4〜6行目は文字列の両方か一方が空文字列の場合の対応です。別に無くても問題に対しては関係ありません。
8〜10行目で動的計画法で使用する2次元配列を初期化しています。Wikipediaの疑似コードは1刻みで初期化していますが、基準となる距離を2に変更するので2刻みにします。
14〜32行目が改造部分です。
14行目は削除、追加の候補値を設定しています。
15行目からはWikipediaの疑似コードは三項演算子で同じなら0、異なれば1にしている部分ですが、問題の仕様では異なる場合の扱いが複雑なのでif-elseになっています。
15行目は同じ文字の場合です。
17〜18行目は大文字、小文字の違いです。
20〜23行目は入れ替えの場合で"xabx"と"xbax"の入れ替えの前方の文字（赤字部分）を見ている場合です。更に21行目は大文字小文字が一致している場合、22行目は大文字小文字の違う場合を判断しています。
24〜27行目も入れ替えの場合ですが"xabx"と"xbax"の入れ替え部分の後方の文字（赤字部分）を見ている場合の処理になります。
それ以外の場合は不一致扱いになります（29行目）。
返却値はWikipediaの疑似コードでは2次元配列の末尾ですが、私のコードでは最後に改行文字を強制的に付加したので一つ手前の場所になります。