21 lines
523 B
Plaintext
21 lines
523 B
Plaintext
F lcs(a, b)
|
||
V lengths = [[0] * (b.len+1)] * (a.len+1)
|
||
L(x) a
|
||
V i = L.index
|
||
L(y) b
|
||
V j = L.index
|
||
I x == y
|
||
lengths[i + 1][j + 1] = lengths[i][j] + 1
|
||
E
|
||
lengths[i + 1][j + 1] = max(lengths[i + 1][j], lengths[i][j + 1])
|
||
|
||
V result = ‘’
|
||
V j = b.len
|
||
L(i) 1..a.len
|
||
I lengths[i][j] != lengths[i - 1][j]
|
||
result ‘’= a[i - 1]
|
||
R result
|
||
|
||
print(lcs(‘1234’, ‘1224533324’))
|
||
print(lcs(‘thisisatest’, ‘testing123testing’))
|