KMP算法的实现，自行输入主串和子串进行测试

KMP算法，全称Knuth-Morris-Pratt算法，是一种用于字符串匹配的有效算法。它的核心思想是通过预处理模式串（子串），创建一个部分匹配表（也叫失配指针数组或失败函数），避免在主串中回溯。

首先，我们需要准备两个步骤：

1. **构建部分匹配表**：对于模式串的每个字符i，如果它等于前缀串j（0 <= j < i），那么失配指针`lps[i] = j + 1`；否则，我们从头开始寻找最长的前缀与当前字符相同的子串`lps[i]`，直到找到或者达到最左边的非相等位置。

2. **字符串匹配**：在主串中从头开始遍历，用模式串的首字符与主串对应位置比较。如果匹配，就继续往后移动；如果不匹配，就根据`lps`表确定跳转到主串的位置，继续匹配。如果遇到`lps[len(pattern) - 1]`，说明找到了一个匹配，否则检查下一个位置。

以下是一个简单的Python实现，假设`pattern`是子串，`text`是主串：

def build_lps(pattern):
    lps = [0]
    length = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[length]:
            length += 1
            lps.append(length)
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps.append(0)
    return lps

def kmp_search(text, pattern):
    text_len = len(text)
    pattern_len = len(pattern)
    lps = build_lps(pattern)
    i = j = 0
    while i < text_len:
        if j < pattern_len and text[i] == pattern[j]:
            i += 1
            j += 1
        elif j > 0:
            j = lps[j - 1]
        else:
            i += 1
    return j == pattern_len

# 测试示例
if __name__ == "__main__":
    main_str = input("请输入主串：")
    sub_str = input("请输入子串：")
    if kmp_search(main_str, sub_str):
        print(f"子串 '{sub_str}' 存在于主串 '{main_str}' 中")
    else:
        print(f"子串 '{sub_str}' 不在主串 '{main_str}' 中")