1234567891011121314151617181920212223242526272829303132333435363738394041 |
- #!/usr/bin/ruby
- #
- ## https://rosettacode.org/wiki/Levenshtein_distance/Alignment
- #
- func align(s, t) {
- s.chars!.prepend!('^')
- t.chars!.prepend!('^')
- var A = []
- {|i| A[i][0]{@|<d s t>} = (i, s.slice(1, i).join, '~' * i) } << ^s
- {|i| A[0][i]{@|<d s t>} = (i, '-' * i, t.slice(1, 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>}]
- }
- say (var r = align("rosettacode", "raisethysword"))
- assert_eq(r, ['ro-settac-o-de', 'raisethysword-'])
|