# s0 のi-1文字目と s1のj文字目の類似度を返す
def q(c,d)
if c==d
return 2
else
return -1
end
end
# 文字列sをi文字目の前に"-"をgap[i]個出力しながら出力する．
def show_align s,len,gap
for i in 0..len
for k in 1..gap[i]
print "-"
end
if i < len
# s[i..i]は文字列sのi文字目だけからなる長さ1の文字列を取り出す．
print s[i..i]
end
end
# 改行を出力する
puts
end
# 文字列s0とs1のalignmentを出力後に類似度を返す
def alignment s0,s1
# 文字列s0の長さをmに入れる
m=s0.length
n=s1.length
g=-2
# 2次元配列 a をすべての要素を0で初期化して作成する．
a=Array.new(m+1)
for i in 0..m
a[i]=Array.new(n+1,0)
end
for i in 0..m
# 「境界条件」のスライドに従って設定
###### (1) #######
end
for j in 0..n
# 「境界条件」のスライドに従って設定
###### (2) #######
end
for i in 1..m
for j in 1..n
# 「アラインメントの動的計画法の」のスライドに従って，値を設定
# 最大値を取るにはmaxが便利
# [1,3,4].max => 4
###### (3) #######
end
end
gap0=Array.new(m+1,0);
gap1=Array.new(n+1,0);
# 「トレースバック」のスライドを元に gap0, gap1 を埋める
# スライドでは省略されていたが，最後に
# gap0[0]=j
# gap1[0]=i
# を入れる必要がある．
i = m; j = n
while i>0 && j>0
if a[i][j] == a[i][j-1] + g
###### (4) #######
elsif a[i][j] == a[i-1][j-1] + q(s0[i-1],s1[j-1])
###### (5) #######
elsif a[i][j] == a[i-1][j] + g
###### (6) #######
end
end
gap0[0]=j
gap1[0]=i
show_align(s0,m,gap0)
show_align(s1,n,gap1)
a[m][n]
end
スコアは以下のものを使う。
irb(main):122:0> alignment "abcdea","aebcdbae" a-bcdea- aebcdbae => 5 irb(main):123:0> alignment "aaabb","baaa" aaabb baa-a => 0 irb(main):123:0> alignment "aabbbbcc","bbbbccaa" aabbbbcc-- --bbbbccaa => 4