# 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