串-求next数组\n已知目标串为 abcdeabedade 模式串为：abcabca，求next数组

### 回答1：
目标串为 abcdeabedade，模式串为 abcabca，求 next 数组。

next 数组是用来优化 KMP 算法的，它表示模式串中每个前缀的最长公共前后缀的长度。具体求法如下：

1. 初始化 next 数组，next[] = -1，next[1] = 。

2. 从 i = 2 开始，依次计算 next[i]。

3. 假设已知 next[1] 到 next[i-1]，现在要求 next[i]。

4. 如果模式串的第 i 个字符和前面的最长公共前后缀的下一个字符相等，那么 next[i] = next[i-1] + 1。

5. 否则，就需要不断回溯，直到找到一个前缀和后缀相等的位置，或者回溯到了模式串的开头。具体做法是，将 next[i-1] 的值赋给 j，然后不断向前回溯，直到找到一个位置 k，使得模式串的前 k 个字符和后 k 个字符相等，或者回溯到了模式串的开头。此时，next[i] = k。

6. 重复步骤 2 到 5，直到求出 next[n]，其中 n 是模式串的长度。

对于本题，模式串为 abcabca，可以按照上述方法求出 next 数组如下：

next[] = -1，next[1] = ，next[2] = ，next[3] = ，next[4] = 1，next[5] = 2，next[6] = 3，next[7] = 1。

注意，next 数组的下标从 开始，而模式串的下标从 1 开始。

### 回答2：
首先，需要对模式串进行预处理，生成next数组。next数组是指在匹配字符串中，当当前字符与模式串中的字符不匹配时，模式串应该向右移动的最短距离。

该串的next数组为：
a b c a b c a
0 0 0 1 2 3 4

其中，第一个字符的next值为0，第二个字符之前的next值为1，第三个字符之前的next值为2，以此类推。

从第四个字符开始，next值需要根据前面的字符来进行计算。

对于abcabca这个模式串，以第四个字符a为例，前三个字符组成的前缀为abc，后三个字符组成的后缀也为abc。因此，next值为3，表示当第4个字符与目标串的第4个字符不匹配时，模式串应该向右移动3个位置。

同理，对于第五个字符b，前四个字符组成的前缀为abca，后四个字符组成的后缀为bcab，都不匹配，需要继续向前找。发现前三个字符abc和最后三个字符bca匹配，因此next值为3。

对于第六个字符c，前五个字符组成的前缀为abcab，后五个字符组成的后缀为cabca，都不匹配，需要同样向前找到前三个字符abc和最后三个字符bca匹配，因此next值为3。

以此类推，可以得到完整的next数组。

### 回答3：
首先需要明确什么是next数组。next数组也称为部分匹配值数组，用来表示模式串中前缀和后缀的最长公共部分的长度。

在求解next数组时，我们可以使用模式串自身的匹配信息来推导next值。具体算法如下：

1.初始化next数组，令next[0]=-1，next[1]=0。

2.令k=0，j=1。

3.循环计算next值：

(a) 如果j等于0或者p[k]等于p[j]，则令next[j+1]=k+1，k=next[j+1]，j=j+1。

(b) 否则，令k=next[k]，直到k=0或者p[k]=p[j]，然后令next[j+1]=k+1，k=next[j+1]，j=j+1。

4.计算完成后，返回next数组。

以本题为例，要求模式串abcabca的next数组，按照上述算法：

1.先初始化next数组，令next[0]=-1，next[1]=0。

2.令k=0，j=1。

3.循环计算next值：

(a) 当j=2时，由于此时p[k]=a，p[j]=b，不匹配，因此令k=next[k]=-1，j=j+1。

(b) 当j=3时，由于此时p[k]=-1，p[j]=c，不匹配，因此令k=next[k]=-1，j=j+1。

(c) 当j=4时，由于此时p[k]=-1，p[j]=a，不匹配，因此令k=next[k]=-1，j=j+1。

(d) 当j=5时，由于此时p[k]=-1，p[j]=b，不匹配，因此令k=next[k]=-1，j=j+1。

(e) 当j=6时，由于此时p[k]=-1，p[j]=c，不匹配，因此令k=next[k]=-1，j=j+1。

(f) 当j=7时，由于此时p[k]=-1，p[j]=a，与p[1]=a匹配成功，因此令next[j+1]=0，k=next[j+1]=0，j=j+1。

4.计算完成后，得到的next数组为[-1, 0, -1, -1, -1, -1, -1, 0]。

因此，模式串abcabca的next数组为[-1, 0, -1, -1, -1, -1, -1, 0]。