1+ #!/usr/bin/env python
2+ # -*- coding:UTF-8
3+ __author__ = 'shenshijun'
4+
5+ """
6+ 自底向上实现LCS
7+ """
8+
9+
10+ # 使用字典保存子问题的结果
11+ def lcs (list_x ,list_y ):
12+ __len_dict = {}
13+ __ele_dict = {}
14+ end_x = len (list_x )- 1
15+ end_y = len (list_y )- 1
16+ result = __lcs (list_x ,list_y ,end_x ,end_y ,__len_dict ,__ele_dict )
17+ return {
18+ 'length' :result ,
19+ 'lcs' :extra_lcs (__ele_dict ,list_x ,end_x ,end_y )
20+ }
21+
22+
23+ def extra_lcs (ele_dict ,list_x ,end_x ,end_y ):
24+ lcs_list = []
25+ index_x = end_x
26+ index_y = end_y
27+ while True :
28+ cur_direct = ele_dict [(index_x ,index_y )]
29+ if cur_direct == '\\ ' :
30+ lcs_list .append (list_x [index_x ])
31+ index_x -= 1
32+ index_y -= 1
33+ elif cur_direct == '|' :
34+ index_x -= 1
35+ else :
36+ index_y -= 1
37+ if index_x < 0 or index_y < 0 :
38+ break
39+ return reversed (lcs_list )
40+
41+
42+ def __lcs (list_x ,list_y ,end_x ,end_y ,__len_dict ,__ele_dict ):
43+ # 插入-1是为了在后面计算的时候可以不用判断边界情况
44+ for y in xrange (- 1 ,end_y + 1 ):
45+ __len_dict [(- 1 ,y )]= 0
46+
47+ for x in xrange (- 1 ,end_x + 1 ):
48+ __len_dict [(x ,- 1 )]= 0
49+ for x in xrange (0 ,end_x + 1 ):
50+ for y in xrange (0 ,end_y + 1 ):
51+ if list_x [x ]== list_y [y ]:
52+ __len_dict [(x ,y )]= 1 + __len_dict [(x - 1 ,y - 1 )]
53+ __ele_dict [(x ,y )]= "\\ "
54+ elif __len_dict [(x - 1 ,y )]>= __len_dict [(x ,y - 1 )]:
55+ __len_dict [(x ,y )]= __len_dict [(x - 1 ,y )]
56+ __ele_dict [(x ,y )]= '|' ;
57+ else :
58+ __len_dict [(x ,y )]= __len_dict [(x ,y - 1 )]
59+ __ele_dict [(x ,y )]= '-' ;
60+ return __len_dict [(end_x ,end_y )]
61+
62+
63+ def main ():
64+ list_x = ['A' ,'B' ,'C' ,'B' ,'D' ,'A' ,'B' ]
65+ list_y = ['B' ,'D' ,'C' ,'A' ,'B' ,'A' ]
66+ result_dict = lcs (list_x ,list_y )
67+ print result_dict ['length' ]
68+ for char in result_dict ['lcs' ]:
69+ print char
70+
71+
72+ if __name__ == "__main__" :
73+ main ()
