字符串-字符串匹配

Leetcode 28题

1、题目描述

# Given two strings needle and haystack, return the index of the first 
# occurrence of needle in haystack, or -1 if needle is not part of haystack. 
# 
#  
#  Example 1: 
# 
#  
# Input: haystack = "sadbutsad", needle = "sad"
# Output: 0
# Explanation: "sad" occurs at index 0 and 6.
# The first occurrence is at index 0, so we return 0.
#  
# 
#  Example 2: 
# 
#  
# Input: haystack = "leetcode", needle = "leeto"
# Output: -1
# Explanation: "leeto" did not occur in "leetcode", so we return -1.
#  
# 
#  
#  Constraints: 
# 
#  
#  1 <= haystack.length, needle.length <= 10⁴ 
#  haystack and needle consist of only lowercase English characters. 

2、代码实现

class Solution:
    def next(self, needle):
        next_arr = [0] * (len(needle) + 1)
        i = 0
        j = 1
        next_arr[0] = -1
        while j < len(needle):
            if i == -1 or needle[i] == needle[j]:
                i += 1
                j += 1
                next_arr[j] = i
            else:
                i = next_arr[i]
        return next_arr

    def strStr(self, haystack: str, needle: str) -> int:
        next_arr = self.next(needle)
        i = 0
        j = 0
        ix = -1
        while i < len(needle) and j < len(haystack):
            if i == -1 or needle[i] == haystack[j]:
                i += 1
                j += 1
            else:
                while i != -1 and needle[i] != haystack[j]:
                    i = next_arr[i]
        if i == len(needle):
            ix = j-len(needle)
        return ix


# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    so = Solution()
    needle = "abcabcmn"
    haystack = "abcababcabcmncabcmn"
    res = so.strStr(haystack, needle)
    print(res)

3、解题思路

• next数组的构建和匹配的过程都采用双指针的策略。
• 构建next数组，next数组的含义是指记录首位固定的情况下，当前字符之前的最长公共子串的长度。
• next数组用一个while循环就可以实现，如果存在回溯的情况j指针不会移动。
• 在匹配的过程中，如果不匹配要进行回溯。

4、next数组

• 假设模式串是abcabeeeabcabcmncabcmn，abcabe和abcabc匹配时，e和c不匹配。
• 但是abcabe和abcabc存在公共相同的子串abcab，abcab也存在公共子串ab。
• abcabe和abcabc中的ab子串都相同，所以直接使用abcabeeeabcabcmncabcmn匹配。