用python写一段代码实现用KMP算法中的求字串next数组的算法求出串aabaaabaac的next数组。

好的，下面是代码实现：

def get_next(p):
    next_list = [-1] * len(p)
    i, j = 0, -1
    while i < len(p) - 1:
        if j == -1 or p[i] == p[j]:
            i += 1
            j += 1
            next_list[i] = j
        else:
            j = next_list[j]
    return next_list

p = "aabaaabaac"
print(get_next(p))

输出的结果为：[-1, 0, 1, 0, 1, 2, 2, 3, 0, 1]

相关问题

用kmp算法求bbdcfbbdac的next数组

首先，让我们来计算字符串 "bbdcfbbdac" 的 next 数组。

KMP 算法中的 next 数组，用于记录每个字符对应的最长相同前缀和后缀的长度。

下面是求解步骤：
1. 初始化一个长度为 n 的数组 next，其中 n 为字符串的长度。
2. 将 next 设置为 -1，next 设置为 0。
3. 设置两个指针 i 和 j，初始值分别为 2 和 0。
4. 在循环中，当 i 小于 n 时，执行以下操作：
- 如果字符 i-1 和字符 j 相等，则将 next[i] 设置为 j+1，并将 i 和 j 都加 1。
- 如果字符 i-1 和字符 j 不相等，则判断 j 是否大于 0：
- 如果 j 大于 0，则将 j 更新为 next[j]。
- 如果 j 等于 0，则将 next[i] 设置为 0，且将 i 加 1。
5. 返回得到的 next 数组。

以上是求解 "bbdcfbbdac" 的 next 数组的过程。最终得到的 next 数组为 [-1, 0, 0, 0, 0, 0, 1, 2, 0, 1]。

KMP算法求串aaabaaaba的next数组

下面是串aaabaaaba的next数组的求解过程：
1. 首先，next=-1，next=0，因为长度为1的字符串没有真前缀和真后缀。
2. 接下来，我们从i=2开始，依次求解next[i]。由于前面已经求出了next=0，所以我们可以利用next来求解next。此时，模式串为aa，前缀为a，后缀为a，它们相等，所以next=1。
3. 继续求解next。此时，模式串为aaa，前缀为a、aa，后缀为a、aa，它们都不相等，所以next=0。
4. 接下来，我们可以利用next来求解next。此时，模式串为aaab，前缀为a、aa、aaa，后缀为b、ab、aab，它们都不相等，所以next=0。
5. 继续求解next。此时，模式串为aaaba，前缀为a、aa、aaa、aaab，后缀为a、ba、aba、aaba，它们都不相等，所以next=1。
6. 接下来，我们可以利用next[5]来求解next。此时，模式串为aaabaa，前缀为a、aa、aaa、aaab、aaaba，后缀为a、aa、baa、abaa、aabaa，它们都不相等，所以next=1。
7. 继续求解next。此时，模式串为aaabaaa，前缀为a、aa、aaa、aaab、aaaba、aaabaa，后缀为a、aa、aaa、baaa、abaaa、aabaaa，它们都不相等，所以next=2。
8. 最后，我们可以利用next来求解next[8]。此时，模式串为aaabaaab，前缀为a、aa、aaa、aaab、aaaba、aaabaa、aaabaaa，后缀为b、ab、aab、baab、abaab、aabaaab，它们都不相等，所以next=0。
因此，串aaabaaaba的next数组为[-1, 0, 1, 0, 0, 1, 1, 2, 0]。