串"acaba"的 next 数组值为（ ）。

A. 01234 B. 01212 C. 01121 D. 01230

[tag_link]

正确答案：C

在 KMP 算法中，next 数组用于模式匹配失败时的跳转。 根据严蔚敏《数据结构》中的定义，对于模式串 `"acaba"`（下标从 1 开始），`next[1] = 0`。 对于 `j > 1`，`next[j]` 是满足条件 `1 < k < j` 且前 `k-1` 个字符与后 `k-1` 个��符相等的最大 `k` 值； 若不存在这样的 `k`，则 `next[j] = 1`。

具体计算过程如下：

• `j = 1` 时，`next[1] = 0`。 >
• `j = 2` 时，`k` 只能取 1，前 0 个字符与后 0 个字符相等，故 `next[2] = 1`。 >
• `j = 3` 时，`k = 2` 不成立（`'a' ≠ 'c'`），`k = 1` 成立，故 `next[3] = 1`。 >
• `j = 4` 时，`k = 3` 不成立（`"ac" ≠ "ca"`），`k = 2` 成立（`'a' = 'a'`），故 `next[4] = 2`。 >
• `j = 5` 时，`k = 4`、`3`、`2` 均不成立，`k = 1` 成立，故 `next[5] = 1`。 >

因此，next 数组值为 `[0, 1, 1, 2, 1]`，即 `01121`，对应选项 C。 >