若主串s=’abcaabccacabcabcaaaabc’，模式串t=’abcabcaaa’，求出t的next数组，并给出采用kmp算法求子串位置的过程。

### 回答1：
题目要求使用KMP算法求解模式串的next数组，并求出主串中匹配模式串的子串位置的过程。

步骤1：求解模式串的next数组
- 初始化next数组，next[0]=0，i=1，j=0
- 如果j=0或者模式串的i位置字符等于模式串的j位置字符，则next[i]=j+1，i=i+1，j=j+1
- 如果模式串的i位置字符不等于模式串的j位置字符，则令j=next[j-1]
- 重复以上步骤，直到i等于模式串的长度，此时next数组求解完成

模式串的next数组为：[0, 0, 0, 1, 1, 2, 3, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

步骤2：使用KMP算法匹配主串中的模式串
- 初始化i=0，j=0
- 如果模式串的j位置字符等于主串的i位置字符，则i=i+1，j=j+1
- 如果j等于模式串的长度，说明匹配成功，输出匹配子串的起始位置i-j，并令j=next[j-1]进行下一次匹配
- 如果j不等于模式串的长度且模式串的j位置字符不等于主串的i位置字符，则令j=next[j-1]进行下一次匹配
- 重复以上步骤，直到主串中不存在匹配的子串

根据以上算法，主串中匹配模式串的子串起始位置为8，即主串中"abcabcaaa"匹配模式串"abcabcaaa"。

### 回答2：
回答：

1. 求t的next数组

将模式串t依次跟自身匹配，每次移动一位。如果匹配的长度为i，则next[i]的值为前缀和后缀的最大匹配长度。具体求法是，模式串t从前往后分别取前缀和后缀，求它们的最大公共前后缀长度。

t = 'abcabcaaa'
i = 1 时，没有前缀和后缀，next[1] = 0
i = 2 时，前缀为a，后缀为b，没有公共前缀后缀，next[2] = 0
i = 3 时，前缀为ab，后缀为c，没有公共前缀后缀，next[3] = 0
i = 4 时，前缀为abc，后缀为a，公共前后缀为a，next[4] = 1
i = 5 时，前缀为abca，后缀为b，没有公共前缀后缀，next[5] = 0
i = 6 时，前缀为abcab，后缀为ca，没有公共前缀后缀，next[6] = 0
i = 7 时，前缀为abcabc，后缀为aa，公共前后缀为a，next[7] = 1
i = 8 时，前缀为abcabca，后缀为aaa，公共前后缀为aaa，next[8] = 3
i = 9 时，前缀为abcabcaa，后缀为aa，公共前后缀为aa，next[9] = 2

因此，模式串t的next数组为[0,0,0,1,0,0,1,3,2]。

2. 用kmp算法求子串位置的过程

首先，我们假设主串s和模式串t的长度分别为n和m。然后，我们从s的左端开始，依次匹配t。如果匹配成功，则返回t在s中的起始位置；如果匹配失败，则移动t，使它能够匹配s中下一个未匹配的字符。

具体过程如下：

1）设置两个指针i和j，分别指向s和t的起始位置；

2）如果s[i]等于t[j]，则进入下一个循环；否则，执行j=next[j]；

3）如果j等于m，说明匹配成功，返回i-m+1（即t在s中的起始位置）；否则，如果i等于n，则匹配失败，返回-1；否则，将i和j都加1，继续匹配。

具体实现见下方代码：

def kmp(s, t):
n, m = len(s), len(t)
if m == 0:
return 0
next = get_next(t)
i, j = 0, 0
while i < n and j < m:
if j == -1 or s[i] == t[j]:
i, j = i+1, j+1
else:
j = next[j]
if j == m:
return i-m
return -1

def get_next(t):
m = len(t)
j, k = 0, -1
next = [-1] * m
while j < m-1:
if k == -1 or t[j] == t[k]:
j, k = j+1, k+1
if t[j] == t[k]:
next[j] = next[k]
else:
next[j] = k
else:
k = next[k]
return next

结果为：t在s中的起始位置为10。

注意：本题还有一种更快的KMP算法实现方式，它可以预处理出t的next数组，而不是每次都重新计算。上述代码中的get_next函数即为预处理next数组。

### 回答3：
在KMP算法中，需要用到Next数组，即对于模式串t的每个位置i，表示以模式串的i为结尾的子串中，前缀和后缀最长的公共长度，称为Next[i]。下面是模式串t=’abcabcaaa’的Next数组：

t a b c a b c a a a

Next 0 0 0 1 2 3 4 0 1

求解Next数组的过程如下：

首先Next[0]=0是确定的。

假设已知了Next[i-1]，现在需要求Next[i]。

如果t[i]=t[Next[i-1]]，那么Next[i]=Next[i-1]+1。

如果不相等，那么找到Next[Next[i-1]-1]，继续比较，重复此过程直到找到相等的位置或者Next[i]=0。

这样，得到了模式串t的Next数组，为[0,0,0,1,2,3,4,0,1]。

接下来是求解主串s中是否存在模式串t的过程，具体如下：

将模式串t的第一个字符与主串s的第一个字符比较，如果相同则继续，否则将模式串t向右移动1位。

将模式串t的第二个字符与主串s的当前字符比较，如果相同则继续，否则根据t的前缀和后缀的最长公共长度，来决定将模式串t向右移动几位。

重复以上步骤，直到找到模式串t在主串s中的所有出现位置或者主串已经比较完毕。

例如，主串s=’abcaabccacabcabcaaaabc’，模式串t=’abcabcaaa’，根据Next数组可知，t的前缀和后缀的最长公共长度为[0,0,0,1,2,3,4,0,1]。接下来开始匹配过程：

1.将t[0]和s[0]比较，不同，将模式串t向右移动1位。

2.将t[index=1]=b和s[index=0]比较，不同，根据Next[0]=0，将模式串t向右移动1位。

3.将t[index=1]=a和s[index=0]比较，相同，继续匹配。

4.将t[index=2]=c和s[index=1]比较，不同，根据Next[1]=0，将模式串t向右移动1位。

5.将t[index=2]=c和s[index=1]比较，不同，根据Next[0]=0，将模式串t向右移动1位。

6.将t[index=2]=c和s[index=1]比较，相同，继续匹配。

……

13.将t[index=8]=a和s[index=14]比较，不同，根据Next[7]=4，将模式串t向右移动4位。

14.将t[index=4]=a和s[index=14]比较，相同，继续匹配。

15.将t[index=5]=b和s[index=15]比较，相同，继续匹配。

16.将t[index=6]=c和s[index=16]比较，相同，继续匹配。

17.将t[index=7]=a和s[index=17]比较，相同，继续匹配。

18.将t[index=8]=a和s[index=18]比较，相同，匹配成功，返回匹配到的位置为12。

因此，模式串t=’abcabcaaa’在主串s=’abcaabccacabcabcaaaabc’中从位置12开始匹配成功。