私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ワイルドカード文字列を推定しよう」（CodeIQ）を参照してください。
ファイルをマウスでぽちぽちと選択しながら、「これらと似たようなファイルを自動的に選択できないかなぁ…」と思った経験はありませんか？
もちろん、OSの標準機能としてワイルドカード文字列による検索は出来ますが、今回はそうではなく逆にユーザーが選んだ複数のファイルのパス名から、何をまとめて選びたいか意図を汲み取り、その結果をワイルドカード文字列として返すというプログラムを考えてみたいと思います。
本設問で求められるプログラムの前提条件は、以下の通りとなります。
標準入力から、ファイルパス名が、パス名の個数分複数行送られる
パス名は、制御コードを含まないASCII文字列で構成される
パス名の長さは、5文字(byte)以上20文字以下である
パス名の個数は、２個以上４個以下である
入力されるすべてのパス名の最長共通部分列（Wikipediaへのリンク）を求め、任意のパス名から最長共通部分列を除いた文字を'*'（アスタリスク）に置き換えたものを、ワイルドカード文字列とすること。
ただしその際、ワイルドカード文字列内に'*'が連続する場合は、'*'1文字に置き換えること。
なお、最長共通部分列は必ず一意になることを前提とする。Wikipediaの例にもあるように、”ABC” と ”ACB” の最長共通部分列は ”AB” と ”AC” の両方であるが、そのような入力は与えられない。
また、ワイルドカードも必ず一意になることを前提とする。例えば、”ABBC”と”ABC”の期待されるワイルドカードは、”AB*C”と”A*BC”の両方となるが、そのような入力は与えられない。
求めたワイルドカード文字列を標準出力に送ること
入力 出力 file01.txt
file02.txt
file11.txt
file*.txt dir_a/doc_a.txt
dir_b/doc_a0.txt
dir_b/doc_a1.txt
dir_a/img_a.png
dir_*/*_a*.*
いかがでしょうか？
残りのファイルを自動的に選択するような機能はまだどのOSにも入っていないと思うのですが、こうしてみるとまだまだOSも賢くなれるような気がしませんか？
それでは、ぜひ挑戦してみてくださいね。
【問題】
標準入力から、複数のファイルパス名が、パス名の個数分複数行送られます。
似たような文字の並びのファイルを自動選択できるよう、入力されるすべてのパス名の最長共通部分列を用いて単一のワイルドカード文字列を求め、その結果を標準出力に返してください。
Rubyで解答しています。
#!/usr/bin/ruby
def getLcs(lcs, a, b, i, j, str)
if (i == 0) || (j == 0) then
return str
end
if a[i-1] == b[j-1] then
str = a[i-1] + str
ret = getLcs(lcs, a, b, i-1, j-1, str)
else
if lcs[i-1][j] >= lcs[i][j-1] then ret = getLcs(lcs, a, b, i-1, j, str)
else ret = getLcs(lcs, a, b, i, j-1, str)
end
end
return ret
end
def calcLcs(a, b)
lcs = Array.new(a.size+1){ Array.new(b.size+1, 0) }
for i in 1..a.size
for j in 1..b.size
if a[i-1] == b[j-1] then x = 1
else x = 0
end
lcs[i][j] = [lcs[i-1][j-1] + x, lcs[i-1][j], lcs[i][j-1]].max
end
end
return lcs
end
def padding(a, b)
ret = ""
i = 0
for j in 0...b.size
if i >= a.size then
ret += '*'
elsif a[i] == b[j] then
ret += a[i]
i += 1
elsif a[i] == '*' then
ret += '*'
i += 1
else
ret += '*'
end
end
if i < a.size then
ret += a[i..-1]
end
return ret
end
def paddingAll(mstr, strs)
padded = []
for str in strs
padded << padding(mstr, str).gsub(/\*+/, "*")
end
return padded.max{|a, b| a.size <=> b.size}
end
def solve(strs)
sorted = strs.sort{|a,b| a.size <=> b.size}
a = sorted.pop
while !sorted.empty?
b = sorted.pop
lcs = calcLcs(a, b)
a = getLcs(lcs, a, b, a.size, b.size, "")
end
ret = paddingAll(a, strs)
return ret
end
# main
inputs = []
while line = gets
line.strip!
next if line.empty?
inputs << line
end
puts solve(inputs)
★★★の問題です。
難しいです。LCS（最長共通部分列）自体は調べればわかりやすい解説が見つかるのでそれほど問題ではありません。
問題は*にする部分を決める方法です。
問題にある通り、まずLCS（最長共通部分列）を求めます。
動的計画法でできます。
私は次のサイト最長共通部分列問題 (Longest Common Subsequence)を参考にしました。
説明は上記サイトが詳しいのでそちらを見てください。
LCSが分かっても、それをワイルドカードを含む文字列にするのが結構な難問です。
例えば、2つ目の例のLCSは"dir_/_a."ですが、これをどうやって"dir_*/*_a*.*"にするかです。
私は次の様な方法でやりました。
まず、LCSである"dir_/_a."と各入力値を1文字ずつ比べて、入力値にあってLCSにない文字の場所を*にします。
dir_a/doc_a.txt → dir_*/***_a.***
dir_b/doc_a0.txt → dir_*/***_a*.***
dir_b/doc_a1.txt → dir_*/***_a*.***
dir_a/img_a.png → dir_*/***_a.***
*が2以上の場所は*1個にします。
dir_a/doc_a.txt → dir_*/*_a.*
dir_b/doc_a0.txt → dir_*/*_a*.*
dir_b/doc_a1.txt → dir_*/*_a*.*
dir_a/img_a.png → dir_*/*_a.*
この中で最長の文字数のものを答えとします。
これであらゆる場合に正しいかは自信が有りません。
入力値を配列にしてsolve()に渡します。
戻り値を印字します。
入力値を文字列の長さで昇順にソートします。
一番短いものをLCSの候補とし、2つ目以降とcalclcs()で比較してLCSを更新します。これを全ての入力値に対して行います。
LCSが決まったらそれと入力値の各文字列をpaddingAll()で比較して*を補充し、最も長い文字列を取得します。
これを答えとして返します。
| a | b | c | ||
| 0 | 0 | 0 | 0 | |
| a | 0 | |||
| c | 0 |
| a | b | c | ||
| 0 | 0 | 0 | 0 | |
| a | 0 | 1 | 1 | 1 |
| c | 0 | 1 | 1 | 2 |
claclcs()で作った表からLCSを作ります。
表の右下から左上に向かって同じ文字の場所を探すという方法でできます。
引数lcsはcalslcs()で作った表です。
a, bは2つの文字列です。
i, jはチェック対象の座標（i行, j列）です。
構築中のstrはLCS文字列です。
座標(0,0)になったら終わりなのでstrを返却します。
aとbの文字を比較し、同じならstrの先頭に追加し、i,jを1減らしてgetLcs()を再帰呼び出しします。
文字が違ったら、現在の座標の上か左のうちlscの値が大きい方に移動してgetLcs()を再帰呼び出しします（同値なら上）。
再帰呼び出しが戻ってきたらLCSが得られます。
mstrはLCS文字列です。
strsは入力値の文字列を長さで昇順にソートしたものです。
strsの各文字列strとmstrをpadding()で比較し、strに文字があってmstrにない場所を*で埋めた文字列を得ます。複数の*が並ぶ場所は正規表現を使って*1個にしてしまいます。
それをpaddedに保持し、paddedの中で最長のものを返します。
aはLCS文字列、bは入力値の文字列のうち1つです。
iは文字列aの現在フォーカスしている文字の位置、jはbの現在フォーカスしている文字の位置です。
retは*で埋められた文字列です。
bの文字列を1個ずつ見ながらaの文字と比較します。
i >= a.sizeの場合、つまりaの長さを超えた時は末尾に*が必要です。
a[i] == b[j]ならその場所は*ではなく特定の文字です。iを1増やしてaのフォーカス位置を進めます。
a[i] == '*'の場合、bの任意の文字と一致したことになるので*を増やし、aのフォーカス位置を進めます。
それ以外はaのフォーカス位置を動かさず、*を追加します。
ループを抜けた時、iがaの長さ未満なら評価されなかったaの部分文字列をretに加えます。
retを返却します。
LCSに関しては調べればわかったのでそれほど難しくはなかったのですが、*で埋めるのが難問でした。
diffでやっているのと同じことなんだろうと思って調べて見ましたがよくわからなかったので解答のような実装になりました。
パターンによってはダメな場合があるように思えてなりません。