题目描述

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从0开始）。如果 needle 不是 haystack 的一部分，则返回 -1

测试用例

输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。

输入：haystack = "aabaabaafa", needle = "aabaaf" 输出：3 解释："aabaaf" 在下标 3 处匹配 所以返回 3

代码实现

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
  let next = getNext(needle);
  let j = -1;
  for (let i = 0; i < haystack.length; i++) {
    while (j >= 0 && haystack[i] !== needle[j + 1]) {
      j = next[j];
    }
    if (haystack[i] === needle[j + 1]) {
      j++;
    }
    if (j === needle.length - 1) {
      return i - needle.length + 1;
    }
  }
  return -1;
};

function getNext(s) {
  let next = new Array(s.length);
  next[0] = -1;
  let j = -1;
  for (let i = 1; i < s.length; i++) {
    while (j >= 0 && s[i] != s[j + 1]) {
      j = next[j];
    }
    if (s[i] === s[j + 1]) {
      j++;
    }
    next[i] = j;
  }
  return next;
}

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入haystack: ");
let haystack = readline();

console.log("请输入needle: ");
let needle = readline();

const res = strStr(haystack, needle);
console.log("res: ", res);

/* 
  请输入haystack:
  aabaabaafa
  请输入needle:
  aabaaf
  res:  3
*/