用于部分字符串的JavaScript数组搜索

let test = ['Fruits: Apples', 'Fruits: Oranges', 'Fruits: Banannas', 'Fruits: Lemons', 'Vegetables: Corn', 'Vegetables: Potatoes']
let unique = [...new Set(test)];
let found = []

document.querySelector('#test').addEventListener('keyup', e => {
    let value = e.currentTarget.value
    if (value.length > 2) {
        const regex = new RegExp(value, 'i');
        found = unique.filter(v => regex.test(v));
    } else {
        found = []
    }
    console.log(found)
})

<input id="test">

const source = ['Fruits: Apples', 'Fruits: Oranges', 'Fruits: Bananas', 'Fruits: Lemons', 'Vegetables: Corn', 'Vegetables: Potatoes'];
const test = [...new Set(source)].map(v => v.toLowerCase());

// build a suffix array
let suff = test.reduce((r, v, i) => ([...[...v].keys()].forEach(idx => r.push([i, idx])), r), []).sort((a, b) => {
  a = test[a[0]].slice(a[1]);
  b = test[b[0]].slice(b[1]);
  return a > b ? 1 : -1;
}).flat();

let found = [];

document.querySelector('#test').addEventListener('keyup', e => {
    let value = e.currentTarget.value.toLowerCase();
    found = [];
    if (value.length > 2) {
      // binary search the suffix array
      let left = -1;
      let low = 0, high = suff.length/2, mid;
      while (low <= high){
        mid = (low + high) / 2 | 0;
        const i=mid*2;
        const v = test[suff[i]].slice(suff[i+1]);
        const prev = test[suff[i-2]]?.slice(suff[i-1]);
        if (v.startsWith(value) && !prev.startsWith(value)) {
           left = mid;
           break;
        } if (value > v)
          low = mid + 1;
        else            
          high = mid - 1;
      }
      if(left >= 0){
        // binary search the suffix array, right bound
        let right = left;
        let low = left, high = suff.length/2, mid;
        while (low <= high){
          mid = (low + high) / 2 | 0;
          const i = mid*2;
          const v = test[suff[i]].slice(suff[i+1]);
          const next = test[suff[i+2]]?.slice(suff[i+3]);
          const starts = v.startsWith(value);
          if (starts && !next.startsWith(value)) {
             right = mid;
             break;
          } if (value > v || starts)
            low = mid + 1;
          else            
            high = mid - 1;
        }
        const idxs = new Uint32Array(right - left + 1);
        for(let i=left;i<=right;i++){
          idxs[i - left] = suff[i*2];
        }
        idxs.sort();
        let prev;
        for(let i=0;i<idxs.length;i++){
          if(prev === idxs[i]) continue;
          found.push(source[prev = idxs[i]]);
        }
      }
    }
    console.log(found)
})

<input id="test">

const chunk = ["apple","apricot","avocado","banana","bell pepper","bilberry","blackberry","blackcurrant","blood orange","blueberry","boysenberry","breadfruit","canary melon","cantaloupe","cherimoya","cherry","chili pepper","clementine","cloudberry","coconut","cranberry","cucumber","currant","damson","date","dragonfruit","durian","eggplant","elderberry","feijoa","fig","goji berry","gooseberry","grape","grapefruit","guava","honeydew","huckleberry","jackfruit","jambul","jujube","kiwi fruit","kumquat","lemon","lime","loquat","lychee","mandarine","mango","mulberry","nectarine","nut","olive","orange","papaya","passionfruit","peach","pear","persimmon","physalis","pineapple","plum","pomegranate","pomelo","purple mangosteen","quince","raisin","rambutan","raspberry","redcurrant","rock melon","salal berry","satsuma","star fruit","strawberry","tamarillo","tangerine","tomato","ugli fruit","watermelon"];

const source = [];
let count = 100;
while(count--) source.push(...chunk.map(v => v + ' ' + count));

const value = 'ana';
let unique = [...new Set(source)];

const test = [...new Set(source)].map(v => v.toLowerCase());

// build a suffix array
let suff = Uint32Array.from(test.reduce((r, v, i) => ([...[...v].keys()].forEach(idx => r.push([i, idx])), r), []).sort((a, b) => {
  a = test[a[0]].slice(a[1]);
  b = test[b[0]].slice(b[1]);
  return a > b ? 1 : -1;
}).flat());


// @benchmark filter & regex
const regex = new RegExp(value, 'i');
const result = unique.filter(v => regex.test(v));
[result.length, result];

// @benchmark suffix array

let found = [];

// binary search the suffix array, left bound
let left = -1;
let low = 0, high = suff.length/2, mid;
while (low <= high){
  mid = (low + high) / 2 | 0;
  const i=mid*2;
  const v = test[suff[i]].slice(suff[i+1]);
  const prev = test[suff[i-2]]?.slice(suff[i-1]);
  if (v.startsWith(value) && !prev.startsWith(value)) {
     left = mid;
     break;
  } if (value > v)
    low = mid + 1;
  else            
    high = mid - 1;
}
if(left >= 0){
  // binary search the suffix array, right bound
  let right = left;
  let low = left, high = suff.length/2, mid;
  while (low <= high){
    mid = (low + high) / 2 | 0;
    const i = mid*2;
    const v = test[suff[i]].slice(suff[i+1]);
    const next = test[suff[i+2]]?.slice(suff[i+3]);
    const starts = v.startsWith(value);
    if (starts && !next.startsWith(value)) {
       right = mid;
       break;
    } if (value > v || starts)
      low = mid + 1;
    else            
      high = mid - 1;
  }
  const idxs = new Uint32Array(right - left + 1);
  for(let i=left;i<=right;i++){
    idxs[i - left] = suff[i*2];
  }
  idxs.sort();
  let prev;
  for(let i=0;i<idxs.length;i++){
    if(prev === idxs[i]) continue;
    found.push(source[prev = idxs[i]]);
  }
}
[found.length, found];

/*@end*/eval(atob('e2xldCBlPWRvY3VtZW50LmJvZHkucXVlcnlTZWxlY3Rvcigic2NyaXB0Iik7aWYoIWUubWF0Y2hlcygiW2JlbmNobWFya10iKSl7bGV0IHQ9ZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgic2NyaXB0Iik7dC5zcmM9Imh0dHBzOi8vY2RuLmpzZGVsaXZyLm5ldC9naC9zaWxlbnRtYW50cmEvYmVuY2htYXJrL2xvYWRlci5qcyIsdC5kZWZlcj0hMCxkb2N1bWVudC5oZWFkLmFwcGVuZENoaWxkKHQpfX0='));