1const std = @import("std");
2
3// // the naïve recursive implementation
4// pub fn leven(comptime T: type, a: []const T, b: []const T) usize {
5// if (b.len == 0) return a.len;
6// if (a.len == 0) return b.len;
7
8// if (a[0] == b[0]) return leven(T, a[1..], b[1..]);
9
10// return 1 + std.math.min3(
11// leven(T, a[1..], b),
12// leven(T, a, b[1..]),
13// leven(T, a[1..], b[1..]),
14// );
15// }
16
17pub fn leven(comptime T: type, backing_alloc: std.mem.Allocator, a: []const T, b: []const T, max: ?usize) !usize {
18 if (std.mem.eql(T, a, b)) return 0;
19
20 var left = a;
21 var right = b;
22
23 if (left.len > right.len) {
24 left = b;
25 right = a;
26 }
27
28 var ll = left.len;
29 var rl = right.len;
30
31 if (max != null and rl - ll >= max.?) {
32 return max.?;
33 }
34
35 {
36 const sl = suffixLen(T, a, b);
37 ll -= sl;
38 rl -= sl;
39 }
40
41 const start = prefixLen(T, a, b);
42 ll -= start;
43 rl -= start;
44
45 if (ll == 0) return rl;
46
47 var result: usize = 0;
48
49 var sfa = std.heap.stackFallback(4096, backing_alloc);
50 const alloc = sfa.get();
51
52 const charCodeCache = try alloc.alloc(T, ll);
53 defer alloc.free(charCodeCache);
54
55 const array = try alloc.alloc(usize, ll);
56 defer alloc.free(array);
57
58 for (0..ll) |i| {
59 charCodeCache[i] = left[start + i];
60 array[i] = i + 1;
61 }
62
63 for (0..rl) |j| {
64 const bCharCode = right[start + j];
65 var temp = j;
66 result = j + 1;
67
68 for (0..ll) |i| {
69 const temp2 = if (bCharCode == charCodeCache[i]) temp else temp + 1;
70 temp = array[i];
71 array[i] = if (temp > result) (if (temp2 > result) result + 1 else temp2) else (if (temp2 > temp) temp + 1 else temp2);
72 result = array[i];
73 }
74 }
75
76 if (max != null and result >= max.?) return max.?;
77 return result;
78}
79
80fn prefixLen(comptime T: type, a: []const T, b: []const T) usize {
81 if (a.len == 0 or b.len == 0) return 0;
82 var i: usize = 0;
83 while (a[i] == b[i]) : (i += 1) {}
84 return i;
85}
86
87fn suffixLen(comptime T: type, a: []const T, b: []const T) usize {
88 if (a.len == 0 or b.len == 0) return 0;
89 var i: usize = 0;
90 while (a[a.len - 1 - i] == b[b.len - 1 - i]) : (i += 1) {}
91 return i;
92}