设目标串t="abcaabbabcabaacbacba",模式串为p="abcabaa"。 （1）计算模式串p的next和nextval值； （2） 画出利用KMP算法进行模式匹配的全部过程。

（1）首先，我们需要计算模式串`p="abcabaa"`的next数组，这是一个动态规划的过程。next[i]表示以字符串`s[p[i]]`结尾的最长前缀和`p[0:i]`相等的部分长度。

- `next[0] = 0`，因为前缀空串和空串一样。
- `next[1] = 0`，因为'a'没有比它更长的前缀。
- `next[2] = 0`，同样道理，'b'没有前缀。
- 对于`p[3] = 'c'`，它的最长前缀`"c"`与`p[0:2]`不符，所以`next[3] = 0`.
- `p[4] = 'a'`，找到了与`p[0:3]`相同的前缀`"aca"`，所以`next[4] = 3`.
- `p[5] = 'b'`，最长前缀仍然是`"aca"`，`next[5] = 3`.
- `p[6] = 'a'`，同理，`next[6] = 4`，因为与`p[0:6]`相等的最长前缀为`"abcabaa"`。
- 继续这个过程直到遍历完整个模式串，得到`next`数组：

   next = [0, 0, 0, 0, 3, 3, 4]

- 接着计算nextval，它是通过next数组索引来更新当前匹配失败后的偏移量。初始时，如果匹配成功，`nextval`始终为0，但如果匹配失败，`nextval`等于`next[j]`，其中`j`是当前字符的位置，使得`p[j] != s[i+next[j]]`。在这个例子中，由于我们还没开始匹配，所以`nextval`数组也是空的。

（2）接下来，我们将利用KMP算法对目标串`t="abcaabbabcabaacbacba"`进行匹配：

- 初始化：设i=0（目标串起始位置），j=0（模式串起始位置），同时记录下当前`nextval`和`next`值。
- 遍历目标串，对于每个字符`s[i]`：
- 如果`s[i] == p[j]`，那么i++, j++。继续下一个字符。
- 如果`s[i] != p[j]`，比较`next[j]`和`i`的大小：
- 如果`next[j] > i`，说明当前模式已经发生错误，但可能是由于之前的错误造成的。回溯到`s[i - next[j]]`处，即`j = next[j]`，然后尝试下一个字符。
- 如果`next[j] <= i`，模式错误，将j更新为`next[j]`，再次检查`s[i]`是否等于`p[j]`。

模拟匹配过程如下：

   t: a b c a a b b a b a c a b a c a
   p: a b c a a b a

   i=0: 匹配成功 (a)
   i=1: 匹配成功 (b)
   i=2: 匹配成功 (c)
   i=3: 匹配成功 (a), j=4
   i=4: 匹配成功 (b), j=5
   i=5: 匹配成功 (a), j=6 (match)

   ... (匹配过程中可能有跳过的情况)
   i=9: 匹配失败 (c) -> 使用nextval (j=next[6]=4), 到i-4=5检查
   i=5: 匹配成功 (a) -> j=4 (still match)

   ... (继续匹配直至结束或找到所有匹配)

注意，在实际过程中，如果模式串在目标串中找不到完全匹配，KMP算法会返回匹配的起始位置或者-1（如果没有匹配）。这个过程展示了如何利用`next`数组优化匹配性能，避免无谓的回溯。