24 lines
1.1 KiB
Text
24 lines
1.1 KiB
Text
s1@(Sequence traits) longestCommonSubsequenceWith: s2@(Sequence traits)
|
|
[| lengths |
|
|
lengths: (ArrayMD newWithDimensions: {s1 length `cache. s2 length `cache} defaultElement: 0).
|
|
s1 doWithIndex: [| :elem1 :index1 |
|
|
s2 doWithIndex: [| :elem2 :index2 |
|
|
elem1 = elem2
|
|
ifTrue: [lengths at: {index1 + 1. index2 + 1} put: (lengths at: {index1. index2}) + 1]
|
|
ifFalse: [lengths at: {index1 + 1. index2 + 1} put:
|
|
((lengths at: {index1 + 1. index2}) max: (lengths at: {index1. index2 + 1}))]]].
|
|
([| :result index1 index2 |
|
|
index1: s1 length.
|
|
index2: s2 length.
|
|
[index1 isPositive /\ index2 isPositive]
|
|
whileTrue:
|
|
[(lengths at: {index1. index2}) = (lengths at: {index1 - 1. index2})
|
|
ifTrue: [index1: index1 - 1]
|
|
ifFalse: [(lengths at: {index1. index2}) = (lengths at: {index1. index2 - 1})]
|
|
ifTrue: [index2: index2 - 1]
|
|
ifFalse: ["assert: (s1 at: index1 - 1) = (s2 at: index2 - 1)."
|
|
result nextPut: (s1 at: index1 - 1).
|
|
index1: index1 - 1.
|
|
index2: index2 - 1]]
|
|
] writingAs: s1) reverse
|
|
].
|