def generate_bad_char_shift(pattern):
    """
    生成坏字符跳转表
    """
    bad_char = {}
    for i in range(len(pattern)):
        bad_char[pattern[i]] = i
    return bad_char
 
def bm_search(text, pattern):
    """
    实现BM算法的简化版本，只使用坏字符规则
    """
    m = len(pattern)
    n = len(text)
 
    if m > n:
        return -1
 
    bad_char = generate_bad_char_shift(pattern)
 
    # 从模式串的末尾开始匹配
    i = m - 1
    while i < n:
        k = i
        j = m - 1
        while j >= 0 and text[k] == pattern[j]:
            k -= 1
            j -= 1
 
        if j == -1:  # 匹配成功
            return k + 1
 
        # 坏字符规则：如果字符在模式串中不存在，移动m个位置
        # 如果存在，移动到该字符在模式串中最后一次出现的位置的后一位
        bad_char_shift = j - (bad_char.get(text[k], -1) if text[k] in bad_char else -1)
        i += max(1, bad_char_shift)  # 至少移动1位
 
    return -1  # 没有找到匹配
 
# 测试
text = "HERE IS A SIMPLE EXANMPLE"
pattern = "EXAMPLE"
result = bm_search(text, pattern)
print("Pattern found at index:", result)

ZGVmIGdlbmVyYXRlX2JhZF9jaGFyX3NoaWZ0KHBhdHRlcm4pOgogICAgIiIiCiAgICDnlJ/miJDlnY/lrZfnrKbot7PovazooagKICAgICIiIgogICAgYmFkX2NoYXIgPSB7fQogICAgZm9yIGkgaW4gcmFuZ2UobGVuKHBhdHRlcm4pKToKICAgICAgICBiYWRfY2hhcltwYXR0ZXJuW2ldXSA9IGkKICAgIHJldHVybiBiYWRfY2hhcgoKZGVmIGJtX3NlYXJjaCh0ZXh0LCBwYXR0ZXJuKToKICAgICIiIgogICAg5a6e546wQk3nrpfms5XnmoTnroDljJbniYjmnKzvvIzlj6rkvb/nlKjlnY/lrZfnrKbop4TliJkKICAgICIiIgogICAgbSA9IGxlbihwYXR0ZXJuKQogICAgbiA9IGxlbih0ZXh0KQogICAgCiAgICBpZiBtID4gbjoKICAgICAgICByZXR1cm4gLTEKCiAgICBiYWRfY2hhciA9IGdlbmVyYXRlX2JhZF9jaGFyX3NoaWZ0KHBhdHRlcm4pCgogICAgIyDku47mqKHlvI/kuLLnmoTmnKvlsL7lvIDlp4vljLnphY0KICAgIGkgPSBtIC0gMQogICAgd2hpbGUgaSA8IG46CiAgICAgICAgayA9IGkKICAgICAgICBqID0gbSAtIDEKICAgICAgICB3aGlsZSBqID49IDAgYW5kIHRleHRba10gPT0gcGF0dGVybltqXToKICAgICAgICAgICAgayAtPSAxCiAgICAgICAgICAgIGogLT0gMQoKICAgICAgICBpZiBqID09IC0xOiAgIyDljLnphY3miJDlip8KICAgICAgICAgICAgcmV0dXJuIGsgKyAxCgogICAgICAgICMg5Z2P5a2X56ym6KeE5YiZ77ya5aaC5p6c5a2X56ym5Zyo5qih5byP5Liy5Lit5LiN5a2Y5Zyo77yM56e75YqobeS4quS9jee9rgogICAgICAgICMg5aaC5p6c5a2Y5Zyo77yM56e75Yqo5Yiw6K+l5a2X56ym5Zyo5qih5byP5Liy5Lit5pyA5ZCO5LiA5qyh5Ye6546w55qE5L2N572u55qE5ZCO5LiA5L2NCiAgICAgICAgYmFkX2NoYXJfc2hpZnQgPSBqIC0gKGJhZF9jaGFyLmdldCh0ZXh0W2tdLCAtMSkgaWYgdGV4dFtrXSBpbiBiYWRfY2hhciBlbHNlIC0xKQogICAgICAgIGkgKz0gbWF4KDEsIGJhZF9jaGFyX3NoaWZ0KSAgIyDoh7PlsJHnp7vliqgx5L2NCgogICAgcmV0dXJuIC0xICAjIOayoeacieaJvuWIsOWMuemFjQoKIyDmtYvor5UKdGV4dCA9ICJIRVJFIElTIEEgU0lNUExFIEVYQU5NUExFIgpwYXR0ZXJuID0gIkVYQU1QTEUiCnJlc3VsdCA9IGJtX3NlYXJjaCh0ZXh0LCBwYXR0ZXJuKQpwcmludCgiUGF0dGVybiBmb3VuZCBhdCBpbmRleDoiLCByZXN1bHQp