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

一、暴力解法

  • 思路：
    • 遍历主字符串 haystack，对于每个字符，尝试从该位置开始与模式字符串 needle 进行逐字符匹配。
    • 若在某一位置能完整匹配上 needle，则返回该位置作为第一个匹配项的下标；若遍历完整个 haystack 都未找到完整匹配，则返回 -1。
  • 示例代码片段：
1
2
3
4
5
6
def strStr(haystack, needle):
    m, n = len(haystack), len(needle)
    for i in range(m - n + 1):
        if haystack[i:i + n] == needle:
            return i
    return -1
  • 时间复杂度：在最坏情况下，对于主字符串 haystack 的每个字符都要尝试进行长度为 len(needle) 的匹配，所以时间复杂度为 ，其中 是 haystack 的长度， 是 needle 的长度。
  • 空间复杂度：只用到了常数级别的额外空间，所以空间复杂度为 。

    二、KMP 算法（Knuth-Morris-Pratt 算法）

  • 思路：
    • KMP 算法主要利用了已经匹配过的部分信息来避免不必要的重新匹配。
    • 首先通过预处理模式字符串 needle，构建一个 next 数组（也叫部分匹配表），它记录了模式字符串自身在不同位置上的最长公共前后缀长度。
    • 在匹配过程中，当主字符串 haystack 和模式字符串 needle 在某一位置不匹配时，利用 next 数组快速将模式字符串的指针移动到合适位置继续匹配，而不是像暴力解法那样每次都从头开始重新匹配模式字符串。
  • 示例代码片段（以 Python 为例）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def strStr(haystack, needle):
    m, n = len(haystack), len(needle)
    if n == 0:
        return 0

    next = [0] * n
    self.buildNext(needle, next)

    p, q = 0, 0
    while p < m and q < n:
        if q == -1 or haystack[p] == needle[q]:
            p += 1
            q += 1
        else:
            q = next[q]

    if q == n:
        return p - n
    return -1

def buildNext(self, needle, next):
    n = len(needle)
    next[0] = -1
    k, j = -1, 0
    while j < n - 1:
        if k == -1 or needle[j] == needle[k]:
            k += 1
            j += 1
            next[j] = k
        else:
            k = next[k]
  • 时间复杂度：预处理 next 数组的时间复杂度为 ，其中 是模式字符串 needle 的长度。在匹配过程中，指针最多移动 次（ 是主字符串 haystack 的长度），所以整体时间复杂度为 。
  • 空间复杂度：除了存储主字符串和模式字符串本身的空间外，需要一个长度为 n 的 next 数组来辅助计算，所以空间复杂度为 。

三、其他优化思路及变体

  • 有些解法可能会基于编程语言的内置函数进行巧妙实现。比如在 Python 中，可以利用字符串的 find 方法直接求解，但这在实际面试等场景中可能不符合考察通过算法实现的本意。
  • 还有一些可能是对 KMP 算法的进一步优化或采用类似思路但实现细节略有不同的算法，比如改进 next 数组的计算方式以提高效率等。
    总体而言，本题主要考察对字符串匹配算法的掌握，从简单直接的暴力解法到更高效的 KMP 算法及其变种等，不同解法在时间和空间复杂度上各有优劣。