LeetCode - 28 找出字符串中第一个匹配的下标

比眉伴天荒 2023-10-12 19:19 5阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

[28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）][28. _ - _LeetCode]

### 题目描述 ###

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

### 示例 ###

示例 1：

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

示例 2：

> 输入：haystack = "leetcode", needle = "leeto"  
> 输出：-1  
> 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

### 提示 ###

*  1 <= haystack.length, needle.length <= 10^4
 *  haystack 和 needle 仅由小写英文字符组成

### 题目解析 ###

本题是经典的KMP算法，关于KMP算法请看：

[算法设计 - KMP算法\_伏城之外的博客-CSDN博客][- KMP_-CSDN]

### Java算法源码 ###

class Solution {
      public int strStr(String haystack, String needle) {
          return indexOf(haystack, needle);
      }
    
      /**
       * @param s 正文串
       * @param t 模式串
       * @return 在s中查找与t相匹配的子串，如果成功找到，则返回匹配的子串第一个字符在主串中的位置
       */
      public static int indexOf(String s, String t) {
        int[] next = getNext(t);
    
        int i = 0; // 扫描S串的指针
        int j = 0; // 扫描T串的指针
    
        // 如果 i 指针扫描到S串结束位置，或者 j 指针扫描到T串的结束位置，都应该结束查找
        while (i < s.length() && j < t.length()) {
          // 如果 s[i] == t[j]，则当前位置匹配成功，继续匹配下一个位置
          if (s.charAt(i) == t.charAt(j)) {
            i++;
            j++;
          } else {
            // 如果 s[i] != t[j]，则说明当前位置匹配失败，
            // 根据KMP算法，我们只需要回退T串的 j 指针到 next[j-1]位置,即最长相同前缀的结束位置后面一个位置，而S串的 i 指针保持不动
            if (j > 0) {
              j = next[j - 1];
            } else {
              // 如果 j = 0,则说明S子串subS和T在第一个字符上就匹配不上, 此时T不匹配字符T[j]前面已经没有前后缀了，因此只能匹配下一个S子串
              i++;
            }
          }
        }
    
        // 如果最终可以在S串中找到匹配T的子串，则T串的所有字符都应该被j扫描过，即最终 j = t.length
        if (j == t.length()) {
          // 则S串中匹配T的子串的首字符位置应该在 i - t.length位置，因为 i 指针最终会扫描到S串中匹配T的子串的结束位置的后一个位置
          return i - j;
        } else {
          // 否则就是没有在S中找到匹配T的子串
          return -1;
        }
      }
    
      public static int[] getNext(String t) {
        int[] next = new int[t.length()];
    
        // 由于是将T串看出两部分，分别是后缀部分SS，和前缀部分TT
        int j = 1; // j 用于扫描SS，由于含有前、后缀的串长度至少为2，因此 j 扫描后缀部分的话，至少从1开始
        int k = 0; // k 用于扫描TT
    
        // j 扫描结束
        while (j < t.length()) {
          if (t.charAt(j) == t.charAt(k)) {
            next[j] = k + 1;
            j++;
            k++;
          } else {
            if (k > 0) {
              k = next[k - 1];
            } else {
              j++;
            }
          }
        }
    
        return next;
      }
    }

[找出字符串中第一个匹配项的下标 - 提交记录 - 力扣（LeetCode）][- _ - _LeetCode]

### JS算法源码 ###

/**
     * @param {string} haystack
     * @param {string} needle
     * @return {number}
     */
    var strStr = function(haystack, needle) {
        return indexOf(haystack, needle);
    };
    
    /**
     * @param {*} s 正文串
     * @param {*} t 模式串
     * @returns 在s中查找与t相匹配的子串，如果成功找到，则返回匹配的子串第一个字符在主串中的位置
     */
    function indexOf(s, t) {
      let next = getNext(t);
    
      let i = 0; // 扫描S串的指针
      let j = 0; // 扫描T串的指针
    
      // 如果 i 指针扫描到S串结束位置，或者 j 指针扫描到T串的结束位置，都应该结束查找
      while (i < s.length && j < t.length) {
        if (s[i] == t[j]) {
          // 如果 s[i] == t[j]，则当前位置匹配成功，继续匹配下一个位置
          i++;
          j++;
        } else {
          // 如果 s[i] != t[j]，则说明当前位置匹配失败，
          // 根据KMP算法，我们只需要回退T串的 j 指针到 next[j-1]位置,即最长相同前缀的结束位置后面一个位置，而S串的 i 指针保持不动
          if (j > 0) {
            j = next[j - 1];
          } else {
            // 如果 j = 0,则说明S子串subS和T在第一个字符上就匹配不上, 此时T不匹配字符T[j]前面已经没有前后缀了，因此只能匹配下一个S子串
            i++;
          }
        }
      }
    
      // 如果最终可以在S串中找到匹配T的子串，则T串的所有字符都应该被j扫描过，即最终 j = t.length
      if (j >= t.length) {
        // 则S串中匹配T的子串的首字符位置应该在 i - t.length位置，因为 i 指针最终会扫描到S串中匹配T的子串的结束位置的后一个位置
        return i - j;
      } else {
        // 否则就是没有在S中找到匹配T的子串
        return -1;
      }
    }
    
    function getNext(t) {
      const next = new Array(t.length).fill(0);
    
      let i = 1;
      let j = 0;
    
      while (i < t.length) {
        if (t[i] == t[j]) {
          next[i] = j + 1;
          i++;
          j++;
        } else {
          if (j > 0) {
            j = next[j - 1];
          } else {
            i++;
          }
        }
      }
    
      return next;
    }

[找出字符串中第一个匹配项的下标 - 提交记录 - 力扣（LeetCode）][- _ - _LeetCode 1]

### Python算法源码 ###

class Solution(object):
        def strStr(self, haystack, needle):
            """
            :type haystack: str
            :type needle: str
            :rtype: int
            """
            return indexOf(haystack, needle)
    
    def getNext(t):
        next = [0] * len(t)
    
        j = 1
        k = 0
    
        while j < len(t):
            if t[j] == t[k]:
                next[j] = k + 1
                j += 1
                k += 1
            else:
                if k > 0:
                    k = next[k - 1]
                else:
                    j += 1
    
        return next
    
    
    def indexOf(s, t):
        """
        :param s: 正文串
        :param t: 模式串
        :return: 在s中查找与t相匹配的子串，如果成功找到，则返回匹配的子串第一个字符在主串中的位置
        """
    
        next = getNext(t)
    
        # 手算的T串"cabaa"对应的前缀表
        # next = [0, 0, 0, 0, 0]
    
        i = 0  # 扫描S串的指针
        j = 0  # 扫描T串的指针
    
        # 如果 i 指针扫描到S串结束位置，或者 j 指针扫描到T串的结束位置，都应该结束查找
        while i < len(s) and j < len(t):
            # 如果 s[i] == t[j]，则当前位置匹配成功，继续匹配下一个位置
            if s[i] == t[j]:
                i += 1
                j += 1
            else:
                # 如果 s[i] != t[j]，则说明当前位置匹配失败
                # 根据KMP算法，我们只需要回退T串的 j 指针到 next[j-1]位置,即最长相同前缀的结束位置后面一个位置，而S串的 i 指针保持不动
                if j > 0:
                    j = next[j - 1]
                else:
                    # 如果 j = 0,则说明S子串subS和T在第一个字符上就匹配不上, 此时T不匹配字符T[j]前面已经没有前后缀了，因此只能匹配下一个S子串
                    i += 1
    
        # 如果最终可以在S串中找到匹配T的子串，则T串的所有字符都应该被j扫描过，即最终 j = t.length
        if j >= len(t):
            # 则S串中匹配T的子串的首字符位置应该在 i - t.length位置，因为 i 指针最终会扫描到S串中匹配T的子串的结束位置的后一个位置
            return i - j
        else:
            # 否则就是没有在S中找到匹配T的子串
            return -1

[找出字符串中第一个匹配项的下标 - 提交记录 - 力扣（LeetCode）][- _ - _LeetCode 2]

[28. _ - _LeetCode]: https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
[- KMP_-CSDN]: https://blog.csdn.net/qfc_128220/article/details/131311563?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22131311563%22%2C%22source%22%3A%22qfc_128220%22%7D
[- _ - _LeetCode]: https://leetcode.cn/submissions/detail/441416653/
[- _ - _LeetCode 1]: https://leetcode.cn/submissions/detail/441416694/
[- _ - _LeetCode 2]: https://leetcode.cn/submissions/detail/441416707/