作业2: 设目标串 s=“abcababcabaa”,模式串 t=“abccaba”。 I (1)计算模式串t的 next数组。

在字符串搜索中，next 数组是一个用来提高模式匹配效率的工具，它是由模式串（t）预先计算出来的。next 数组的每个元素表示模式串中与前面的子串相匹配的最长相同前缀和后缀的长度。如果不存在这样的前缀和后缀，则该元素值为 -1。

对于模式串 t = "abccaba"，我们可以按照以下步骤计算它的 next 数组：

1. 初始化 next 数组为 -1，因为空字符串与任何字符串的匹配长度都是 -1。
2. 从模式串的第二个字符开始，尝试找到与当前字符之前的所有字符相匹配的最长前后缀。
3. 对于每个位置，计算 next 值。

下面是计算过程：

模式串 t:   a   b   c   c   a   b   a
next数组：   -1   0   0   0   1   2   3

解释：

• t[1] 前没有字符，所以 next[1] = 0。
• t[2] 之前的字符是 a，它们没有公共前后缀，所以 next[2] = 0。
• t[3] 之前的子串是 b 和 c，没有公共前后缀，所以 next[3] = 0。
• t[4] 之前的子串是 bc，c 是 bc 的一个后缀，所以 next[4] = 1。
• t[5] 之前的子串是 bca，a 是 bca 的一个后缀，但是更长的 ba 也是 bca 的后缀，所以 next[5] = 2。
• t[6] 之前的子串是 abca，ab 是 abca 的一个前缀，也是 abca 的一个后缀，所以 next[6] = 3。

这样我们就得到了模式串 t 的 next 数组。在实际的字符串搜索算法中，如 KMP（Knuth-Morris-Pratt）算法，这个数组将被用来在不匹配的情况下跳过尽可能多的字符，从而提高搜索效率。