KMP算法next'

KMP算法中的next数组是用于记录模式串中每个字符匹配失败后需要回退的位置。next'数组则是next数组的优化版本，用于进一步减少匹配次数。next'数组的求解过程与next数组类似，只是在回退的过程中，将模式串中相同的前缀和后缀进行了一些优化。

具体求解next'数组的步骤如下：
1. 初始化next' = -1、next' = 0。
2. 设置两个指针i和j，分别指向模式串的第1个字符和第2个字符，即i = 1、j = 2。
3. 进入循环，判断两种情况：
a. 如果sub[i-1] = sub[j-1]，则next'[j] = next'[i] + 1，然后i++、j++，继续下一轮循环。
b. 如果sub[i-1] != sub[j-1]，则将i回退到next'[i]指示的位置，并继续判断。
4. 重复步骤3，直到j = lenSub，其中lenSub是模式串的长度。

最后，得到的next'数组即为KMP算法中的优化next数组。通过使用next'数组进行匹配时，可以进一步减少模式串与主串的匹配次数，提高匹配效率。

相关问题

kmp算法next计算方法C语言,KMP(next)算法c语言实现

KMP算法中的next数组计算方法如下：

void getNext(char *p, int *next) {
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1) {
        if (k == -1 || p[j] == p[k]) {
            ++j;
            ++k;
            if (p[j] != p[k]) {
                next[j] = k;
            } else {
                next[j] = next[k];
            }
        } else {
            k = next[k];
        }
    }
}

KMP算法的C语言实现如下：

#include <stdio.h>
#include <string.h>

void getNext(char *p, int *next);
int kmp(char *s, char *p);

int main() {
    char s[100], p[100];
    printf("请输入主串：");
    scanf("%s", s);
    printf("请输入模式串：");
    scanf("%s", p);
    int pos = kmp(s, p);
    if (pos == -1) {
        printf("未找到匹配的子串\n");
    } else {
        printf("匹配的子串起始位置为：%d\n", pos);
    }
    return 0;
}

void getNext(char *p, int *next) {
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1) {
        if (k == -1 || p[j] == p[k]) {
            ++j;
            ++k;
            if (p[j] != p[k]) {
                next[j] = k;
            } else {
                next[j] = next[k];
            }
        } else {
            k = next[k];
        }
    }
}

int kmp(char *s, char *p) {
    int sLen = strlen(s);
    int pLen = strlen(p);
    int next[pLen];
    getNext(p, next);
    int i = 0, j = 0;
    while (i < sLen && j < pLen) {
        if (j == -1 || s[i] == p[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    if (j == pLen) {
        return i - j;
    } else {
        return -1;
    }
}

KMP算法 next数组

KMP算法中的next数组是用于优化字符串匹配过程的一种技巧。它的作用是在不匹配时，快速确定下一次匹配尝试的起始位置。

next数组的构建过程如下：
1. 首先，初始化next数组的第一个元素为-1，第二个元素为0。
2. 然后，从第三个元素开始依次计算next值。
3. 对于每个位置i，先找到前一个位置的next值，记为j = next[i-1]。
4. 如果当前位置i的字符和位置j的字符相同，那么next[i] = j + 1。
5. 如果不相同，则继续向前找j的next值，即j = next[j]，直到找到相同的字符或者j为-1。
6. 最后，如果j为-1，则next[i] = 0；否则，next[i] = j + 1。

通过构建好的next数组，可以在模式串与目标串不匹配时，根据next数组的值来确定目标串中下一次匹配尝试的起始位置，从而避免了不必要的比较。

希望这个简要的解释对你有帮助！如果你有其他问题，请随时提出。