暴力枚举法

时间复杂度：

- 外层循环遍历了所有可能的起始位置，时间复杂度为 O(len(T)-len(S)+1)

- 内层循环遍历了字符串 S 的所有字符，时间复杂度为 O(len(S))

- 总时间复杂度为 O((len(T)-len(S)+1) * len(S)) ------------ 这里不满足题目要求

空间复杂度：

- 使用了常数个变量，空间复杂度为 O(1)

class Solution:
    def find(self , S: str, T: str) -> int:
        # write code here
        res = 0  # 出现的次数
        for i in range(len(T)-len(S)+1):
            temp = T[i:i+len(S)]
            temp_res = 0
            for j in range(len(S)):
                if S[j] == temp[j]:
                    temp_res += 1
                else:
                    break
            if temp_res == len(S):
                res += 1
        return res

KMP算法

求next数组

# 最长公共前后缀，求next数组
class Solution(object):
    def longestCommonPrefixAndSuffix(self, strs):
        n = len(strs)
        next = [0]*n
        j = 0  # 要比较的下标
        i = 1  # 当前的下标
        while i < n:
            if strs[i] == strs[j]:  # 如果当前值与被比较值相等
                j += 1
                next[i] = j
                i += 1
            else: # 当前值与被比较值不相等
                if j > 0:    # 没有匹配到头j>0，j=next[j-1]
                    j = next[j-1]
                elif j == 0: # 匹配到头j=0，当前值next[i] = 0 or =j, 然后当前值索引+1
                    next[i] = 0
                    i += 1
        return next
obj = Solution()
print(obj.longestCommonPrefixAndSuffix('ababcabaa'))    # [0, 0, 1, 2, 0, 1, 2, 3, 1]


# 也可以进一步改进成：
# 最长公共前后缀
class Solution(object):
    def longestCommonPrefixAndSuffix(self, s):
        n = len(s)
        # 构建 next 数组
        next = [0] * n
        j = 0
        for i in range(1, n):
            while j > 0 and s[i] != s[j]:
                j = next[j - 1]
            if s[i] == s[j]:
                j += 1
            next[i] = j
        print(next)
obj = Solution()
print(obj.longestCommonPrefixAndSuffix('ababcabaa'))  # [0, 0, 1, 2, 0, 1, 2, 3, 1]

KMP应用next数组求解

# 计算模板串S在文本串T中出现了多少次
# @param S string字符串 模板串, 子串
# @param T string字符串 文本串, 主串
# @return int整型
class Solution:
    def kmp(self , S: str, T: str) -> int:
        # write code here
        '构造next数组'
        '''伪代码
            if S[i]==S[j]:
                i++,j++,next[i]=j
            elif S[i]!=S[j]
                if j==0, next[i]=0=j,i++
                elif j!=0, j = next[j-1]
        '''
        j = 0 # 被比较的下标，初始化为0
        next = [0]*len(S)
        for i in range(1, len(S)): # i循环下标，初始化为1
            if S[i] == S[j]:
                j += 1
                next[i] = j
            else: 
                if j != 0:
                    while j != 0 and S[i] != S[j]:
                        j = next[j-1]
                else: 
                    next[i] = j
        '子串S去匹配主串T'
        '''伪代码
        如果两个串的对应字符相等，索引都+1
        如果不相等，子串的j=0时，主串的索引i+1；j不等于0时，j = next[j-1]
        如果子串循环完成，次数+1，同时更新j，j = next[j-1]
        '''
        i, j = 0, 0
        res = 0 # 次数
        while i < len(T):
            if T[i] == S[j]:
                i+=1
                j+=1
            else:
                if j > 0:
                    j = next[j-1]
                else: # j == 0, 头一个就匹配失败
                    i += 1
            if j == len(S):
                res += 1 # 出现次数+1
                j = next[j-1]
        return res