4.2 Brute Force 算法

[giscus[bot]]

4.2 Brute Force 算法

Brute Force 算法 1. Brute Force 算法介绍 Brute Force 算法：简称为 BF 算法。中文意思是暴力匹配算法，也可以叫做朴素匹配算法。 BF 算法思想：对于给定文本串 T 与模式串 p，从文本串的第一个字符开始与模式串 p 的第一个字符进行比较，如果相等，则继续逐个比较后续字符，否则从文本串 T 的第二个字符起重新和模...

https://algo.itcharge.cn/04_string/04_02_string_brute_force/

[sys-xander]

我还以为是啥很厉害的算法，原来是暴力匹配0.0

[youpingfang]

还有 另外一种写法：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # 获取主串（haystack）和子串（needle）的长度
        haylen = len(haystack)
        needlen = len(needle)
        
        # 特殊情况处理：
        # 1. 主串长度小于子串长度，直接返回-1（不可能匹配）
        if haylen < needlen:
            return -1
        # 2. 子串为空串，按LeetCode题目约定返回0（空串是任何串的子串）
        if needlen == 0:
            return 0
        
        # 遍历主串的所有可能起始位置（i最大为 haylen - needlen，避免子串越界）
        for i in range(haylen - needlen + 1):
            # 用于遍历子串的索引j
            j = 0
            # 逐字符对比主串当前位置（i+j）与子串位置（j）
            while j < needlen:
                # 若某字符不匹配，跳出循环，尝试主串下一个起始位置
                if haystack[i + j] != needle[j]:
                    break
                # 字符匹配，继续对比下一个字符
                j += 1
            # 若j遍历完整个子串（j == needlen），说明完全匹配，返回当前起始索引i
            if j == needlen:
                return i
        
        # 遍历所有可能后仍未匹配，返回-1
        return -1