经典题目

字符串匹配

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

示例1:

输入：haystack = "hello", needle = "ll"
输出：2

示例2:

输入：haystack = "aaaaa", needle = "bba"
输出：-1

示例3:

输入：haystack = "", needle = ""
输出：0

思路:

通过 needle 创建前缀表 next 数组
定义变量
- i 记录访问的 haystack 字符
- j 记录访问的 needle 字符
如果 haystack[i]==needle[j] 时: j++
如果 haystack[i]!=needle[j] 时: j 要取 j 前一个字符所对应的前缀表值即 next[j-1]
如果 j==needle.length 时，说明已经遍历完 needle ，i-needle.length+1 即为所求的索引值

:::details 点击查看代码

function getNext(s){
  let j=0;
  let next=[j];
  for(let i=1;i<s.length;i++){
    while(j>0&&s[i]!=s[j]){
      j=next[j-1]
    }
    if(s[i]==s[j]){
      j++
    }
    next[i]=j
  }
  return next
}
function strStr(haystack,needle){
  let hLen=haystack.length;
  let nLen=needle.length;
  if(!nLen){
    return 0
  }
  let j=0;
  let next=getNext(needle);
  for(let i=0;i<hLen;i++){
    while(j>0&&haystack[i]!=needle[j]){
      j=next[j-1]
    }
    if(haystack[i]==needle[j]){
      j++
    }
    if(j==nLen){
      return i-nLen+1
    }
  }
  return -1
}
const haystack='aabaabaaf';
const needle='aabaaf'
// const haystack='a';
// const needle='a'
// const haystack='';
// const needle="";
console.log(strStr(haystack,needle));

:::

字符串匹配​

字符串匹配