KMP算法的经典题目

以下是一道经典的 KMP 题目：

给定一个文本串 T 和一个模式串 P，求模式串 P 在文本串 T 中出现的次数。

输入格式：
第一行输入整数 n，表示文本串 T 的长度。
第二行输入字符串 T。
第三行输入整数 m，表示模式串 P 的长度。
第四行输入字符串 P。

输出格式：
输出一个整数，表示模式串 P 在文本串 T 中出现的次数。

输入样例：
8
abababab
2
ab

输出样例：
4

这道题可以使用 KMP 算法来解决，具体思路是：

1. 首先使用 KMP 算法对模式串 P 进行预处理，得到其 next 数组。

2. 然后在文本串 T 上使用 KMP 算法进行匹配，具体思路是：从文本串 T 的第一个字符开始，依次读入每个字符，如果当前字符与模式串 P 的某个字符不匹配，则根据 next 数组回溯到模式串 P 的某个位置重新开始匹配。

3. 如果在文本串 T 上匹配到了一个完整的模式串 P，则将匹配次数加 1，然后继续从下一个字符开始匹配。

最终匹配次数即为模式串 P 在文本串 T 中出现的次数。

下面是 Python 代码实现：

def kmp(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0:
        return 0
    next = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = next[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        next[i] = j
    res = 0
    j = 0
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = next[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            res += 1
            j = next[j - 1]
    return res

n = int(input())
text = input().strip()
m = int(input())
pattern = input().strip()
print(kmp(text, pattern))