题解 | #公共子串计算#

分析

s1: asd
s2: werasd
定义 map[i][j] 为s1[0..i]，s2[0..j]的最长子串长度

转移方程

P(i,j) = P(i-1,j-1) + 1

代码

str_tmp = []
str_tmp << gets.strip
str_tmp << gets.strip 
str1 ,str2 = '', ''
if str_tmp.first.size < str_tmp.last.size 
    str1, str2 = str_tmp
else 
    str2, str1 = str_tmp
end
map = {}
str1.size.times{|i| map[i] = {}}

max_l = 0
str1.size.times do |i| 
   str2.size.times do |j|
       if str1[i] == str2[j]   
            if i-1 >= 0 && j-1 >=0
                map[i][j] = map[i-1][j-1]+1
            else 
                map[i][j] = 1
            end
           max_l = map[i][j] if map[i][j] > max_l
       else 
           map[i][j] = 0
       end
   end
end
puts max_l