“abcabcgd”建立的pnext表是什么

对于字符串 "abcabcgd"，它的 pnext 表可以这样计算：

1. 首先，pnext 表的第一个元素为 -1，表示这个字符串的第一个字符不可能匹配其他任何字符。

2. 接下来，依次计算每个位置的 pnext 值。以位置 i=0 开始，pnext[0] = -1。

3. 对于位置 i=1，我们需要找到与它匹配的最长前缀，也就是最长的 j 满足 j<i 且 pattern[0...j-1] == pattern[i-j...i-1]。由于 j<i，这说明前缀的长度小于 i，因此我们可以从 pnext[j] 中获取一些信息，即 pattern[0...pnext[j]] == pattern[i-pnext[j]...i-1]。此时，需要考虑 pattern[j] 是否能够和 pattern[i] 匹配。如果 pattern[j] == pattern[i]，那么最长前缀的长度就可以增加 1，即 pnext[i] = pnext[j] + 1；否则，我们需要继续找更短的前缀，即 pnext[j]，并重复上述过程，直到找到匹配的前缀或者无法再找到更短的前缀。在本例中，pattern[0...j-1] = "a"，没有前缀与 pattern[1] 匹配，因此 pnext[1] = 0。

4. 对于位置 i=2，同样需要找到与它匹配的最长前缀。此时，最长的 j 是 0，因为它是最短的前缀。但是，pattern[0] != pattern[2]，因此最长前缀的长度为 0，即 pnext[2] = 0。

5. 对于位置 i=3，最长的 j 是 1，此时 pattern[0...j-1] = "a"，因此我们需要判断 pattern[j+1] 是否与 pattern[i] 匹配。由于相等，最长前缀的长度为 2，即 pnext[3] = 2。

6. 对于位置 i=4，最长的 j 是 2，此时 pattern[0...j-1] = "ab"，因此我们需要判断 pattern[j+1] 是否与 pattern[i] 匹配。由于相等，最长前缀的长度为 3，即 pnext[4] = 3。

7. 对于位置 i=5，最长的 j 是 3，此时 pattern[0...j-1] = "abc"，因此我们需要判断 pattern[j+1] 是否与 pattern[i] 匹配。由于不相等，我们需要继续找更短的前缀。由于 j=2，因此我们需要找 pnext[j]，即 pnext[2]。此时，最长的 k 是 -1，因此最长前缀的长度为 0，即 pnext[5] = 0。

8. 对于位置 i=6，最长的 j 是 0，此时没有前缀与 pattern[6] 匹配，因此 pnext[6] = 0。

综上所述，"abcabcgd" 的 pnext 表为 [-1, 0, 0, 2, 3, 0, 0, 0]。