33 lines
993 B
Text
33 lines
993 B
Text
func align(s, t) {
|
|
s.chars!.prepend!('^')
|
|
t.chars!.prepend!('^')
|
|
|
|
var A = []
|
|
{|i| A[i][0]{@|<d s t>} = (i, s.slice(1).first(i).join, '~' * i) } << ^s
|
|
{|i| A[0][i]{@|<d s t>} = (i, '-' * i, t.slice(1).first(i).join) } << ^t
|
|
|
|
for i (1 .. s.end) {
|
|
for j (1 .. t.end) {
|
|
if (s[i] != t[j]) {
|
|
A[i][j]{:d} = 1+(
|
|
var min = Math.min(A[i-1][j]{:d}, A[i][j-1]{:d}, A[i-1][j-1]{:d})
|
|
)
|
|
A[i][j]{@|<s t>} = (A[i-1][j]{:d} == min
|
|
? [A[i-1][j]{:s}+s[i], A[i-1][j]{:t}+'-']
|
|
: (A[i][j-1]{:d} == min
|
|
? [A[i][j-1]{:s}+'-', A[i][j-1]{:t}+t[j]]
|
|
: [A[i-1][j-1]{:s}+s[i], A[i-1][j-1]{:t}+t[j]]))...
|
|
}
|
|
else {
|
|
A[i][j]{@|<d s t>} = (
|
|
A[i-1][j-1]{:d},
|
|
A[i-1][j-1]{:s}+s[i],
|
|
A[i-1][j-1]{:t}+t[j],
|
|
)
|
|
}
|
|
}
|
|
}
|
|
return [A[-1][-1]{@|<s t>}]
|
|
}
|
|
|
|
align("rosettacode", "raisethysword").each { .say }
|