#!/usr/bin/ruby

# Pontuation
Match = 1
Mismatch = -1
Gap = -2

# Scoring function
def score(a,b)
	if (a == b)
		Match
	else
		Mismatch
	end
end

# Tests if i and j and inside the k-strip
def inside_strip?(i,j,k)
	((i-j) >= -k) && ((i-j) <= k)
end

# Function for k-strip around main diagonal
def kband(s,t,k)
	n = s.length
	a = Array.new(n+1) { Array.new(n+1) }
	
	(0..k).each { |i| a[i][0] = i*Gap }
	(0..k).each { |j| a[0][j] = j*Gap }
	
	(1..n).each do |i|
		(-k..k).each do |d|
			j = i + d
			if (j >= 1) && (j <= n)
				a[i][j] = a[i-1][j-1] + score(s[i-1],t[j-1])
				a[i][j] = [a[i][j], a[i-1][j] + Gap].max if inside_strip?(i-1,j,k)
				a[i][j] = [a[i][j], a[i][j-1] + Gap].max if inside_strip?(i,j-1,k)
			end
		end
	end
	
	a[n][n]
end

# Similarity function
# Returns an array containing all the values returned by the KBand function.
def similarity(s,t)
	n = s.length
	k = 1
	x = kband(s,t,k)
	xs = [] << x 
	
	until x >= Match*(n-k-1) + 2*(k+1)*Gap
		k = k*2
		x = kband(s,t,k)
		xs << x
	end
	
	xs
end

p similarity("AGTCGTGACACCTGGGGACTGACTGACTGGGGGACTGACTGACTG",
             "GTCCGTGATGCCAACTGACTGACTGAAACACTGACTGAAACGTCA")