28. Implement strStr()

题目描述：

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 1:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

题目翻译

返回字符串中第一次出现给定字符串的位置

示例1：

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

解题方案

标签： Array

思路：

• 暴力解法对主串元素和子串进行一一遍历比对，时间复杂度为$O(mn)$,$m$为主串长度，$n$为子串长度。

• 使用KMP模式匹配算法，时间复杂度可降为$O(m+n)$，这里主要使用KMP算法。

• 针对传统的模式匹配算法，当子串与主串某一元素不匹配时，子串需要回溯到开始位置，主串开始下一元素的匹配。这样有些子串和主串已经匹配的信息将会丢失，造成冗余匹配。

• KMP算法针对子串计算$next$数组，主串指针不会回退。记主串为$T[0\cdots n-1]$，子串为$P[0\cdots m-1]$。假设主串和子串分别在第$i$和$j$个位置失配($T[i]\ne P[j]$)，那么有$P[0\cdots j-1]=T[i-j\cdots i-1]$,假设下一步主串应该与子串第$k$个字符继续比较(注意主串$i$指针不会回退)，此时有$P[0\cdots k-1]=$ $T[i-k\cdots i-1]$,考虑前面$P[0\cdots j-1]=T[i-j\cdots i-1]$,我们可知对于长度为$k$ 的匹配串有$P[j-k\cdots j-1]=T[i-k\cdots i-1]$ ,那么则有$P[0\cdots k-1]=P[j-k \cdots j-1]$,问题转换为求子串前缀和后缀的最长公共子序列的问题。当主串和子串失配时，仅需将子串向右滑动至第$k$个字符和主串中第$i$个字符对齐即可。

  令$next[j]=k$，表示子串第$j$个字符与主串字符失配时，在子串中需重新和主串中该字符重新进行比较的位置。

  $$next[j]=\left{ \begin{aligned}&-1 &j=0\&max{k|1\le k<j且P[0\cdots k-1]=P[j-k\cdots j-1}\&0&otherwise\end{aligned}\right.$$

• 考虑"ababc"这一字子串

  • "a":$next[0]=-1$；
  • "ab":$next[1]=0$；
  • "aba":前缀[a]后缀[b]，无公共元素，next[2]=0；
  • "abab":前缀为[a, ab]，后缀为[ba, a]，共有元素的长度为1,$next[3]=1$；
  • "ababc"的前缀为[a, ab, aba]，后缀为[bab, ab,a]，最长共有元素为"ab"，长度为2，$next[4]=2$；

代码：

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        next = self.getnext(self, needle)    # 获取next数组
        i = 0    # 主串指针
        j = 0    # 子串指针
        len1 = len(haystack)    # 主串长度
        len2 = len(needle)    # 子串长度
        while i < len1 and j < len2:
            if haystack[i] == needle[j] or j == -1:     # 相等继续向前比较
                i += 1
                j += 1
            else:   # 不等，j 回溯到 next[j]
                j = next[j]
        if j < len2:    # 遍历完，子串仍有空余，即没有找到匹配的位置
            return -1
        else:    # 匹配完成，匹配位置为当前位置-子串长度
            return i-len2

    def getnext(self, needle):  # 获取子串 next 数组，求最长前缀后缀长度，相当于对子串本身进行一次模式匹配
        i = 0
        j = -1
        next = [-1 for i in range(len(needle))]    # next数组初始化为 -1，next[0] = -1
        while i < len(needle) - 1:
            if j == -1 or needle[i] == needle[j]:   # 如果相等，最大前缀后缀长度+1
                i += 1
                j += 1
                next[i] = j
            else:   # 如果不等，j回溯到next[j]
                j = next[j]
        return next

参考资料

• 《数据结构 C++版本(第二版)》王红梅、胡明、王涛编著