字符串查找

问题

实现一个函数，在给定的字符串中查找子串第一次出现的位置。如果找到则返回子串开始的索引位置，如果未找到则返回 -1。这是对原生 indexOf 方法的手动实现，帮助理解字符串匹配的基本原理。

解答

/**
 * 在字符串中查找子串的位置
 * @param {string} str - 主字符串
 * @param {string} target - 要查找的子串
 * @param {number} fromIndex - 开始查找的位置，默认为 0
 * @returns {number} 子串首次出现的索引，未找到返回 -1
 */
function strIndexOf(str, target, fromIndex = 0) {
  // 参数校验
  if (typeof str !== 'string' || typeof target !== 'string') {
    return -1;
  }
  
  // 空字符串特殊处理
  if (target === '') {
    return fromIndex >= 0 && fromIndex <= str.length ? fromIndex : 0;
  }
  
  // 处理起始位置
  const startIndex = fromIndex < 0 ? 0 : fromIndex;
  
  // 如果子串长度大于剩余字符串长度，直接返回 -1
  if (target.length > str.length - startIndex) {
    return -1;
  }
  
  // 遍历主字符串，查找匹配位置
  for (let i = startIndex; i <= str.length - target.length; i++) {
    let match = true;
    
    // 逐字符比较
    for (let j = 0; j < target.length; j++) {
      if (str[i + j] !== target[j]) {
        match = false;
        break;
      }
    }
    
    // 找到匹配，返回索引
    if (match) {
      return i;
    }
  }
  
  // 未找到匹配
  return -1;
}

// 方法二：使用 substring 进行比较（更简洁）
function strIndexOf2(str, target, fromIndex = 0) {
  if (typeof str !== 'string' || typeof target !== 'string') {
    return -1;
  }
  
  if (target === '') {
    return fromIndex >= 0 && fromIndex <= str.length ? fromIndex : 0;
  }
  
  const startIndex = fromIndex < 0 ? 0 : fromIndex;
  
  for (let i = startIndex; i <= str.length - target.length; i++) {
    if (str.substring(i, i + target.length) === target) {
      return i;
    }
  }
  
  return -1;
}

使用示例

// 基本使用
console.log(strIndexOf('hello world', 'world')); // 6
console.log(strIndexOf('hello world', 'o')); // 4
console.log(strIndexOf('hello world', 'xyz')); // -1

// 指定起始位置
console.log(strIndexOf('hello world', 'o', 5)); // 7
console.log(strIndexOf('hello world', 'o', 8)); // -1

// 空字符串情况
console.log(strIndexOf('hello', '')); // 0
console.log(strIndexOf('hello', '', 3)); // 3

// 边界情况
console.log(strIndexOf('abc', 'abcd')); // -1
console.log(strIndexOf('', 'a')); // -1
console.log(strIndexOf('aaa', 'aa')); // 0

// 与原生方法对比
const str = 'JavaScript is awesome';
const target = 'is';
console.log(strIndexOf(str, target) === str.indexOf(target)); // true

关键点

• 双层循环匹配：外层循环遍历主字符串的每个可能起始位置，内层循环逐字符比较子串
• 边界条件处理：
  • 空字符串的特殊处理（返回起始位置）
  • 子串长度大于剩余字符串时直接返回 -1
  • 起始位置的合法性校验
• 优化搜索范围：外层循环只需遍历到 str.length - target.length，避免无效比较
• 提前终止：内层循环发现不匹配时立即 break，提高效率
• 时间复杂度：O(n * m)，其中 n 是主字符串长度，m 是子串长度
• 可选优化：可以使用 KMP、Boyer-Moore 等高级算法将时间复杂度优化到 O(n + m)