kmp算法与bf算法代码

KMP算法（Knuth-Morris-Pratt 算法）是一种字符串匹配算法，用于在一个主串中查找是否存在给定的模式串。它的核心思想是在遇到不匹配字符时，利用已经计算好的部分匹配表（也叫失配函数或前缀表）跳过多余的比较，提高搜索效率。下面是KMP算法的基本伪代码：

function compute_lps(pattern):
    lps = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            lps[i] = j
        else:
            while j > 0 and pattern[i] != pattern[j]:
                j = lps[j - 1]
            if pattern[i] == pattern[j]:
                j += 1
            lps[i] = j
    return lps

function knuth_morris_pratt(text, pattern):
    lps = compute_lps(pattern)
    i = j = 0
    while i < len(text) and j < len(pattern):
        if text[i] == pattern[j]:
            i += 1
            j += 1
        else:
            if j > 0:
                j = lps[j - 1]
            else:
                i += 1
    return j == len(pattern)

BF（Boyer-Moore 搜索算法）则是一个更高效的字符串搜索算法，它结合了坏字符规则和好后缀规则。坏字符规则是基于最后一个不匹配字符的位置来移动；好后缀规则则是当遇到不匹配时，根据最长公共前后缀原则跳到模式串的某个位置继续搜索。BF算法通常比KMP更快，尤其是在文本很大而模式串中有很多重复的情况下。

以下是BF算法的简单Python版本：

def bad_char_rule(pattern, text, index):
    m = len(pattern)
    t = len(text)
    while index + m <= t and text[index + m - 1] != pattern[m - 1]:
        index += 1
    return index

def good_suffix_rule(pattern, text, index):
    skip = 0
    for j in reversed(range(len(pattern))):
        while index >= skip + j and text[index - j] != pattern[j]:
            skip = max(skip, len(pattern) - j - 1)
        if text[index - j] == pattern[j]:
            skip = j
    return index + skip

def boyer_moore_search(pattern, text):
    index = -1
    while True:
        index = bad_char_rule(pattern, text, index + 1) or (index + 1)
        if not index:
            return True
        index = good_suffix_rule(pattern, text, index)
    return False