mod.js 3.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138
  1. const peq = new Uint32Array(0x10000);
  2. const 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. };
  35. const 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. };
  112. const 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. };
  126. const 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. };
  138. export { closest, distance };