↓Skip to main content
  1. Posts/

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

·1 min·
Table of Contents

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

Solution 1 #

KMP 算法模板题. 代码如下:

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def KMP(s, p):
            def build_next(p):
                next = [0]
                prefix_len = 0
                i = 1
                while i < len(p):
                    if p[prefix_len] == p[i]:
                        prefix_len += 1
                        next.append(prefix_len)
                        i += 1
                    elif prefix_len == 0:
                        next.append(0)
                        i += 1
                    else:
                        prefix_len = next[prefix_len - 1]
                return next
            next = build_next(p)
            print(next)
            i, j = 0, 0
            while i < len(s):
                if s[i] == p[j]:
                    i += 1
                    j += 1
                elif j > 0:
                    j = next[j - 1]
                else:
                    i += 1
                if j == len(p):
                    return i - j
            return -1  
        return KMP(haystack, needle)