Anonymous user
Longest common subsequence: Difference between revisions
no edit summary
No edit summary |
|||
Line 1:
{{puzzle}}[[Category:Recursion]]▼
'''<u>1234</u>'''
'''<u>12</u>'''245'''<u>3</u>'''332'''<u>4</u>'''
Line 194 ⟶ 195:
=={{header|Java}}==
===Recursion===
<java>public static String lcs(String a, String b){
if(a.length() == 0 || b.length() == 0){
Line 293 ⟶ 294:
=={{header|Python}}==
===Recursion===
▲[[Category:Recursion]]
This solution is similar to the Haskell's one. It is slow.
<python>def lcs(xstr, ystr):
def lcs(xstr, ystr):▼
"""
>>> lcs('thisisatest', 'testing123testing')
'tsitest'
"""
if not
return ""
x, xs, y, ys = xstr[0], xstr[1:], ystr[0], ystr[1:]
Line 309 ⟶ 306:
return x + lcs(xs, ys)
else:
return
Test it:
<python>
Line 316 ⟶ 312:
import doctest; doctest.testmod()
</python>
===Dynamic Programming===
{{trans|Java}}
lengths = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
# row 0 and column 0 are initialized to 0 already
for i in range(len(a)):
for j in range(len(b)):
if a[i] == b[j]:
lengths[i+1][j+1] = lengths[i][j] + 1
else:
lengths[i+1][j+1] = \
max(lengths[i+1][j], lengths[i][j+1])
# read the substring out from the matrix
result = ""
x, y = len(a), len(b)
while x != 0 and y != 0:
if lengths[x][y] == lengths[x-1][y]:
x -= 1
elif lengths[x][y] == lengths[x][y-1]:
y -= 1
else:
assert a[x-1] == b[y-1]
result = a[x-1] + result
x -= 1
y -= 1
return result</python>
| |||