leetcode | 28.实现strStr()

28.实现strStr()

题目描述

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

思路

1. 直接调用python内置方法

2. 暴力匹配
   让字符串 needle 与字符串 haystack 的所有长度为 m（needle字符串的长度） 的子串均匹配一次。
   为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 −1-1−1。
   3.kmp算法
   kmp算法的目的：为了避免不必要的指针回溯
   主串指针i不回溯，模式串指针j的变化取决于模式串的结构是否有重复
   pi数组值的计算：
   pi数组的值为最长相同前后缀长度+1(串本身不能作为前后缀)
   pi[1]=0,其他情况next[]=1.

   代码

   class Solution:

    """
    kmp算法的目的：为了避免不必要的指针回溯
   
    主串指针i不回溯，模式串指针j的变化取决于模式串的结构是否有重复
   
    pi数组值的计算：
    pi数组的值为最长相同前后缀长度+1(串本身不能作为前后缀)
    pi[1]=0,其他情况next[]=1.
    """
    def strStr(self, haystack: str, needle: str) -> int:
        # 获取主串和模式串的长度
        n = len(haystack)
        m = len(needle)
   
        # 如果模式串的长度为0，则返回0
        if m == 0:
            return 0
   
        pi = [0]*m
   
        # 求模式串的前缀函数值
        i = 1
        j = 0
        while i < m:
            while j > 0 and needle[i] != needle[j]:
                j = pi[j-1]  # 回溯
   
            if needle[i] == needle[j]:
                j += 1
   
            pi[i] = j
   
            i += 1
   
        print("模式串的前缀函数值:", pi)
   
        # kmp
        i = 0
        j = 0
        while i < n:
            while j > 0 and haystack[i] != needle[j]:
                j = pi[j-1]  # 回溯
   
            if haystack[i] == needle[j]:
                j += 1
   
            if j == m:
                return i - m + 1
   
            i += 1
   
        return -1
   
    def strStr1(self, haystack: str, needle: str) -> int:
        """调用内置方法"""
        # 方法1
        # return haystack.find(needle)
   
        # 方法2
        if not needle:
            return 0
   
        try:
            return haystack.index(needle)
        except ValueError:
            return -1
   
    def strStr2(self, haystack: str, needle: str) -> int:
        """暴力匹配"""
        n = len(haystack)
        m = len(needle)
   
        i = 0
   
        while i + m <= n:
            flag = True
   
            j = 0
            while j < m:
                if haystack[i + j] != needle[j]:
                    flag = False
                    break
   
                j += 1
   
            if flag:
                return i
   
            i += 1
        return -1
   

   if name == “main“:

    s = Solution()
    # print(s.strStr("mississippi", "issip"))  # [0, 0, 0, 1, 0]
    # print(s.strStr1("mississippi", "issip"))  # [0, 0, 0, 1, 0]
    print(s.strStr2("mississippi", "issip"))  # [0, 0, 0, 1, 0]