求next数组

求解方法：根据模式串下标分情况计算！

  • 若模式串下标从 “1” 开始

    next 数组中第一位写 0，第二位写 1。

    求解后面每个元组的 next 值时，将该元素A的前一个元素B与其 next 值所对应下标的元素C进行比较：如果B与C相同，则将元素B的 next 值 +1 作为当前元素A的 next 值；否则，将前一个元素B和C的next值所对应的元素进行比较，如果相同，则将元素C的 next 值 +1 作为当前元素A的 next 值，以此重复操作。

    如果找到模式串最前面都找不到相同的元素，则将元素A的 next 值赋为 1。

    过程如下：

    第一步：填入0，1

下标 1 2 3 4 5 6 7 8 9
模式串 a b a a b c a b a
next 0 1

第二步：比较第二个元素和其 next 值所对应下标的元素，不相同。则当前所求第三个元素 next 值赋为 1

在这里插入图片描述

下标 1 2 3 4 5 6 7 8 9
模式串 a b a a b c a b a
next 0 1 1

第三步：比较第三个元素和其 next 值所对应下标的元素，相同。则当前所求第四个元素 next 值为前一个元素的 next 值 +1

在这里插入图片描述

下标 1 2 3 4 5 6 7 8 9
模式串 a b a a b c a b a
next 0 1 1 2

第四步：比较第四个元素和其 next 值所对应下标的元素，不相同。则比较第四个元素与next 值所对应下标的元素（第二个元素）的next值所对应下标的元素（第一个元素）相比较，相等。则当前所求第五个元素 next 值为第四个元素的next值所对应下标的元素（第二个元素）的 next 值 +1

下标 1 2 3 4 5 6 7 8 9
模式串 a b a a b c a b a
next 0 1 1 2 2

后续步骤重复方法即可……

  • 若模式串下标从“0”开始

    next 数组中第一位写 -1，第二位写 0。

    求解后面每个元组的 next 值时，将该元素A的前一个元素B与其 next 值所对应下标的元素C进行比较：如果B与C相同，则将元素B的 next 值 +1 作为当前元素A的 next 值；否则，将前一个元素B和C的next值所对应的元素进行比较，如果相同，则将元素C的 next 值 +1 作为当前元素A的 next 值，以此重复操作。

    如果找到模式串最前面都找不到相同的元素，则将元素A的 next 值赋为 0。

求nextval数组

==手算解题：先计算出next数组，再由next数组求出nextval数组==

1
2
3
4
5
6
7
8
9
10
// 手算对应代码
nextval[1] = 0;
for (int j = 2; j <= T.length(); j++) {
    if (T.ch[next[j]] == T.ch[j]) {
        nextval[j] = nextval[next[j]];
    }
    else {
        nextval[j] = next[j];
    }
}
下标 1 2 3 4 5 6 7 8 9
模式串 a b a a b c a b a
next 0 1 1 2 2 3 1 2 3

如果当前元素与其next值所对应的下标元素相等，则其nextval值为对应下标元素的nextval值；否则等于本身next值。

nextval 0 1 0 2 1 3 0 1 0