class LCS


	@@c=Array.new(100){Array.new(100,0)}
	@@b=Array.new(100){Array.new(100,0)}
	@@zlicz=0
	attr_accessor :x , :y

	def initialize(a,b)
		@x=a
		@y =b
	end


	def PRINTLCS(i,j,x,y)
		if i==0 || j==0
			return
		end

		if @@b[i][j] == 'u'
			PRINTLCS(i-1,j-1,@x,@y)
			print "#{@x[i-1]}"

		elsif @@b[i][j] == 'g'
			PRINTLCS(i-1,j,@x,@y)
		elsif @@b[i][j] == 'b'
			PRINTLCS(i,j-1,@x,@y)
		end
	end


	def LCSLength(x,y)
	i=0
	j=0

	for i in 0..@x.size
		@@c[i][0]=0
		@@b[i][0]='0'
		i=i+1
	end

	for j in 0..@y.size
		@@c[0][j]=0
		@@b[0][j]='0'
		j=j+1
	end

	for i in 1..@x.size

			for j in 1..@y.size
				if @x[i-1]==@y[j-1]
					@@c[i][j]=@@c[i-1][j-1]+1
					@@b[i][j] ='u'
				else
					if @@c[i-1][j] >= @@c[i][j-1]
						@@c[i][j] = @@c[i-1][j]
						@@b[i][j] ='g'
					else

							@@c[i][j]=@@c[i][j-1]
							@@b[i][j]='b'

					end
				end
				j=j+1
			end
			i=i+1
		end

		q=0
		w=0
		print "\n\n\n"

		for q in 0..@x.size
			for w in 0..@y.size
				print "#{@@b[q][w]}"
				w=w+1
			end
			print "\n"
			q=q+1
		end
		print "\n\n\n"

		for q in 0..@x.size
			for w in 0..@y.size
				print "#{@@c[q][w]}"
				w=w+1
			end
			print "\n"
			q=q+1
		end
		print "\n\n\n"

	print "\n i = #{i} , j = #{j} \n"
	print "NWP: "
	PRINTLCS(i-1,j-1,@x,@y)

	end

end
=begin
		print "Podaj 1 ciąg: "
		x =gets.chomp.to_s
		puts"1-szy ciąg bedzie brany pionowo\n\n"
		print "Podaj 2 ciąg: "
		y = gets.chomp.to_s
		puts "2-gi ciąg będzie brany pioziomo\n"
		#x=[1,0,1,1]
		#y =[0,0,1,0,1,0,1,1,1]

objekt = LCS.new(x,y)



print "\n\n\n NWP: "
objekt.LCSLength(x,y)

print "\n\n\n"
=end