js实现indexof功能

实现 JavaScript 的 indexOf 功能

JavaScript 的 indexOf 方法用于返回字符串或数组中指定元素的首次出现位置。以下是手动实现该功能的几种方式：

字符串的 indexOf 实现

function stringIndexOf(str, searchValue, fromIndex = 0) {
  if (fromIndex >= str.length) return -1;
  if (fromIndex < 0) fromIndex = 0;

  for (let i = fromIndex; i < str.length; i++) {
    if (str[i] === searchValue[0]) {
      let match = true;
      for (let j = 0; j < searchValue.length; j++) {
        if (str[i + j] !== searchValue[j]) {
          match = false;
          break;
        }
      }
      if (match) return i;
    }
  }
  return -1;
}

数组的 indexOf 实现

function arrayIndexOf(arr, searchElement, fromIndex = 0) {
  if (fromIndex >= arr.length) return -1;
  if (fromIndex < 0) fromIndex = Math.max(0, arr.length + fromIndex);

  for (let i = fromIndex; i < arr.length; i++) {
    if (arr[i] === searchElement) return i;
  }
  return -1;
}

使用递归实现

function recursiveIndexOf(str, searchValue, fromIndex = 0) {
  if (fromIndex >= str.length) return -1;
  if (str.slice(fromIndex, fromIndex + searchValue.length) === searchValue) {
    return fromIndex;
  }
  return recursiveIndexOf(str, searchValue, fromIndex + 1);
}

性能优化版本

对于大型字符串，可以使用更高效的算法如 KMP 算法：

function kmpIndexOf(str, pattern) {
  const lps = computeLPSArray(pattern);
  let i = 0, j = 0;

  while (i < str.length) {
    if (str[i] === pattern[j]) {
      i++;
      j++;
      if (j === pattern.length) return i - j;
    } else {
      if (j !== 0) j = lps[j - 1];
      else i++;
    }
  }
  return -1;
}

function computeLPSArray(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let len = 0, i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) len = lps[len - 1];
      else {
        lps[i] = 0;
        i++;
      }
    }
  }
  return lps;
}

这些实现涵盖了基本功能到高级优化方案，可以根据具体需求选择合适的版本。原生 indexOf 经过高度优化，手动实现主要用于理解原理或特殊场景定制。