0028. 实现 strStr() #

标签：字符串、双指针
难度：简单

题目大意 #

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置（从 0 开始）。如果不存在，则返回 -1。

解题思路 #

字符串匹配的经典题目。常见的字符串匹配算法有：BF（Brute Force）、RK（Robin-Karp）、KMP（Knuth Morris Pratt）、BM（Boyer Moore）、Sunday 算法等。

代码 #

BF（Brute Force）暴力检索

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        i = 0
        j = 0
        len1 = len(haystack)
        len2 = len(needle)

        while i < len1 and j < len2:
            if haystack[i] == needle[j]:
                i += 1
                j += 1
            else:
                i = i - (j - 1)
                j = 0

        if j == len2:
            return i-j
        else:
            return -1

RK（Robin-Karp）哈希检索

KMP（Knuth Morris Pratt）算法