1const peq = new Uint32Array(0x10000); 2const myers_32 = (a, b) => { 3 const n = a.length; 4 const m = b.length; 5 const lst = 1 << (n - 1); 6 let pv = -1; 7 let mv = 0; 8 let sc = n; 9 let i = n; 10 while (i--) { 11 peq[a.charCodeAt(i)] |= 1 << i; 12 } 13 for (i = 0; i < m; i++) { 14 let eq = peq[b.charCodeAt(i)]; 15 const xv = eq | mv; 16 eq |= ((eq & pv) + pv) ^ pv; 17 mv |= ~(eq | pv); 18 pv &= eq; 19 if (mv & lst) { 20 sc++; 21 } 22 if (pv & lst) { 23 sc--; 24 } 25 mv = (mv << 1) | 1; 26 pv = (pv << 1) | ~(xv | mv); 27 mv &= xv; 28 } 29 i = n; 30 while (i--) { 31 peq[a.charCodeAt(i)] = 0; 32 } 33 return sc; 34}; 35const myers_x = (b, a) => { 36 const n = a.length; 37 const m = b.length; 38 const mhc = []; 39 const phc = []; 40 const hsize = Math.ceil(n / 32); 41 const vsize = Math.ceil(m / 32); 42 for (let i = 0; i < hsize; i++) { 43 phc[i] = -1; 44 mhc[i] = 0; 45 } 46 let j = 0; 47 for (; j < vsize - 1; j++) { 48 let mv = 0; 49 let pv = -1; 50 const start = j * 32; 51 const vlen = Math.min(32, m) + start; 52 for (let k = start; k < vlen; k++) { 53 peq[b.charCodeAt(k)] |= 1 << k; 54 } 55 for (let i = 0; i < n; i++) { 56 const eq = peq[a.charCodeAt(i)]; 57 const pb = (phc[(i / 32) | 0] >>> i) & 1; 58 const mb = (mhc[(i / 32) | 0] >>> i) & 1; 59 const xv = eq | mv; 60 const xh = ((((eq | mb) & pv) + pv) ^ pv) | eq | mb; 61 let ph = mv | ~(xh | pv); 62 let mh = pv & xh; 63 if ((ph >>> 31) ^ pb) { 64 phc[(i / 32) | 0] ^= 1 << i; 65 } 66 if ((mh >>> 31) ^ mb) { 67 mhc[(i / 32) | 0] ^= 1 << i; 68 } 69 ph = (ph << 1) | pb; 70 mh = (mh << 1) | mb; 71 pv = mh | ~(xv | ph); 72 mv = ph & xv; 73 } 74 for (let k = start; k < vlen; k++) { 75 peq[b.charCodeAt(k)] = 0; 76 } 77 } 78 let mv = 0; 79 let pv = -1; 80 const start = j * 32; 81 const vlen = Math.min(32, m - start) + start; 82 for (let k = start; k < vlen; k++) { 83 peq[b.charCodeAt(k)] |= 1 << k; 84 } 85 let score = m; 86 for (let i = 0; i < n; i++) { 87 const eq = peq[a.charCodeAt(i)]; 88 const pb = (phc[(i / 32) | 0] >>> i) & 1; 89 const mb = (mhc[(i / 32) | 0] >>> i) & 1; 90 const xv = eq | mv; 91 const xh = ((((eq | mb) & pv) + pv) ^ pv) | eq | mb; 92 let ph = mv | ~(xh | pv); 93 let mh = pv & xh; 94 score += (ph >>> (m - 1)) & 1; 95 score -= (mh >>> (m - 1)) & 1; 96 if ((ph >>> 31) ^ pb) { 97 phc[(i / 32) | 0] ^= 1 << i; 98 } 99 if ((mh >>> 31) ^ mb) { 100 mhc[(i / 32) | 0] ^= 1 << i; 101 } 102 ph = (ph << 1) | pb; 103 mh = (mh << 1) | mb; 104 pv = mh | ~(xv | ph); 105 mv = ph & xv; 106 } 107 for (let k = start; k < vlen; k++) { 108 peq[b.charCodeAt(k)] = 0; 109 } 110 return score; 111}; 112const distance = (a, b) => { 113 if (a.length < b.length) { 114 const tmp = b; 115 b = a; 116 a = tmp; 117 } 118 if (b.length === 0) { 119 return a.length; 120 } 121 if (a.length <= 32) { 122 return myers_32(a, b); 123 } 124 return myers_x(a, b); 125}; 126const closest = (str, arr) => { 127 let min_distance = Infinity; 128 let min_index = 0; 129 for (let i = 0; i < arr.length; i++) { 130 const dist = distance(str, arr[i]); 131 if (dist < min_distance) { 132 min_distance = dist; 133 min_index = i; 134 } 135 } 136 return arr[min_index]; 137}; 138export { closest, distance }; 139