题解 | #公共子串计算#

公共子串计算

http://www.nowcoder.com/practice/98dc82c094e043ccb7e0570e5342dd1b

分析

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

0 1 2
0 0 - -
1 0 0 -
3 1 0 0
4 0 2 0
5 0 0 3

转移方程

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
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务