找出字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标

leetcode 链接

思路：

前缀表 KMP 算法

1.获取 KMP 前缀表。先遍历模式串 needle，定义两个指针 i, j, 将 j 初始化为-1，赋给 next[0] = j。然后遍历 needle 串，当 needle[i] != needle[j + 1]时，j = next[j], 表示将 j 指针回退到上一个前缀的下一个字符，然后再判断 needle[i] == needle[j + 1]是否成立，如果成立，则 next[i] = j + 1，如果不成立，则继续回退，直到 j = -1，表示没有找到前缀，此时 next[i] = -1。最后返回 next 数组即可。

2.获取到前缀表之后，定义两个指针 i, j，分别指向 haystack 和 needle 的第一个字符，然后循环遍历 haystack，如果 haystack[i] == needle[j]，则 i++, j++，如果 j == needle.length，则表示匹配成功，返回 i - j，如果 haystack[i] != needle[j]，则将 j 回退到 next[j]，然后继续判断 haystack[i] == needle[j]是否成立，如果成立，则 i++, j++，如果不成立，则继续回退，直到 j = -1，表示没有找到前缀，此时 i++, j++，最后返回-1 即可。

typescript 解法

function strStr(haystack: string, needle: string): number {
  const next: number[] = getNext(needle);
  let j: number = -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(str: string): number[] {
  const arr: string[] = str.split("");
  let next: number[] = new Array(arr.length);
  let j = -1;
  next[0] = j;
  for (let i = 1; i < arr.length; i++) {
    while (j >= 0 && arr[i] != arr[j + 1]) {
      j = next[j];
    }
    if (arr[i] == arr[j + 1]) {
      j++;
    }
    next[i] = j;
  }
  return next;
}

go 解法

func strStr(haystack string, needle string) int {
    next := getNext(needle)
    j := -1
    for i := 0; i < len(haystack); i ++ {
        for j >= 0 && haystack[i] != needle[j + 1] { // 不相同，则将next[j]赋值给j
            j = next[j]
        }
        if haystack[i] == needle[j + 1] { // 相同，则i和j均+1
            j ++
        }
        // 如果j的长度等于子串的长度，则说明已找到了匹配项，
        if j == len(needle) - 1 {
            return i - len(needle) + 1
        }
    }
    return -1
}

func getNext(str string) []int {
    lenStr := len(str)
    // next[i] 表示i（包括i）之前最长相等的前后缀长度（其实就是j）
    ret := make([]int, lenStr)
    j := -1
    ret[0] = j
    for i := 1; i < lenStr; i ++ {
        for j >= 0 && str[i] != str[j + 1] { // 前后缀不一样
            j = ret[j] // 向前回退
        }
        if str[i] == str[j + 1] {// 前后缀一样
            j ++
        }
        ret[i] = j // 将当前元素的最大公共前后缀的长度记录下来
    }
    return ret
}