擅长:python、mysql、java
<p>这是我用Python编写的最快的实现:</p>
<pre><code>def lcs(x, y):
'''returns the length of longest common subsequence of x and y.
>>> lcs('abcde','aebd')
3
'''
s_x, s_y = len(x), len(y)
if s_x>s_y:
x, y = y, x
s_x, s_y = s_y, s_x
y_previous = s_x*[0]
for y_char in y:
left_value = 0
diagonal_value = 0
n=0
for x_char in x:
up_value = y_previous[n]
if y_char==x_char:
left_value = diagonal_value+1
else:
if left_value<up_value:
left_value = up_value
diagonal_value = up_value
y_previous[n] = left_value
n+=1
return y_previous[-1]
</code></pre>
<p>如果你想提高性能,你可以用Cython编译它。它跑得快90倍!在</p>
^{pr2}$