[已解决]求助数据结构模式串next数组

极品召唤兽

求aaab的next数组
为什么是0123？
第三个a对不上，第二个不是也对不上吗
为什么不直接是0

最佳答案

月排行榜 / 总排行榜

FishC_GPT

2023-11-29 01:37:46

极品召唤兽 发表于 2023-11-29 01:37
我题目里面说的应该是next数组的优化，求nextval数组 ...

非常抱歉之前的回答仍然存在错误理解。在标准的KMP算法中，next数组记录的是模式串中每个位置上，从该位置开始逐个向前匹配的最长前缀子串的长度。该最长前缀子串必须以当前位置的前一个字符结尾。对于模式串 "aaab"，正确的next数组应该是 [0, 1, 2, 0]。具体步骤如下：
1. 首先，第一个字符 "a" 没有前缀，所以next[0] = 0。
2. 接下来，计算第二个字符 "a" 的next值。它之前只有一个字符 "a"，所以最长前缀子串长度为1，即next[1] = 1。
3. 然后，我们计算第三个字符 "a" 的next值。它之前的两个字符 "aa" 是相等的，所以最长前缀子串长度为2，即next[2] = 2。
4. 最后，计算第四个字符 "b" 的next值。它之前的三个字符 "aab" 中，没有与当前位置的 "b" 相等的前缀子串。因此，next[3] = 0。

所以，模式串 "aaab" 的next数组为 [0, 1, 2, 0]。非常抱歉之前给出的错误答案，希望这次能给你正确的解答。感谢你的指正。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

极品召唤兽

极品召唤兽 发表于 2023-11-29 00:50
虽然结果不太对，但是我知道是啥意思了，就是找到最长的再匹配，第三个位置的a匹配不上，但是前面的都匹 ...

我题目里面说的应该是next数组的优化，求nextval数组的时候是这样的，但是题目问的是next数组，所以是0123不是0003

FishC_GPT

在求解模式串的next数组时，我们需要找到模式串中每个位置上与前面某个位置相同的最长前缀子串的长度。

对于模式串 "aaab"，让我们一步一步来计算它的next数组：

1. 首先，我们可以确定第一个字符 "a" 的next值为0（因为前面没有与其相等的字符）。
2. 然后，我们来计算第二个字符 "a" 的next值。由于前两个字符相等，所以最长前缀子串的长度为1，因此next值为1。
3. 接下来，我们计算第三个字符 "a" 的next值。这里需要注意的是，我们要找到的是与该位置之前的字符相等的最长前缀子串。在这种情况下，前面的两个 "a" 与当前位置的 "a" 相等，但是第三个字符 "b" 与当前位置的 "a" 不相等。所以，最长前缀子串的长度是2，因此next值为2。
4. 最后，我们计算第四个字符 "b" 的next值。在这种情况下，前面的三个字符 "a" 与当前位置的 "b" 都不相等，所以最长前缀子串的长度为0，因此next值为0。

综上所述，模式串 "aaab" 的next数组为 [0, 1, 2, 0]。

关于你的问题，"为什么第三个字符不是0而是2"，这是因为我们在求解next数组时，要找到模式串中与前面某个位置相同的最长前缀子串的长度。对于第三个字符 "a"，虽然它之前的第二个字符也是 "a"，但是它之前的第一个字符 "a" 与当前位置的 "a" 并不相等。因此，我们需要找到与当前位置相等的最长前缀子串的长度，而不是继续往前找不相等的字符。

希望这样的解释能够帮助你理解next数组的计算过程。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

极品召唤兽

FishC_GPT 发表于 2023-11-29 00:43
在求解模式串的next数组时，我们需要找到模式串中每个位置上与前面某个位置相同的最长前缀子串的长度。

对 ...

虽然结果不太对，但是我知道是啥意思了，就是找到最长的再匹配，第三个位置的a匹配不上，但是前面的都匹配上了，就去匹配第二个a，第四个b没匹配上就去找最长的，也就是第三个a再匹配，答案是0123

FishC_GPT

极品召唤兽 发表于 2023-11-29 00:50
虽然结果不太对，但是我知道是啥意思了，就是找到最长 ...

非常抱歉，我之前的回答有误。实际上，模式串 "aaab" 的 next 数组应该是 [0, 1, 2, 0]。

计算 next 数组的正确步骤如下：
1. 首先，我们可以确定第一个字符 "a" 的 next 值为 0（因为前面没有与其相等的字符）。
2. 然后，我们来计算第二个字符 "a" 的 next 值。在这种情况下，前面的一个 "a" 与当前位置的 "a" 相等，所以最长前缀子串的长度为 1，因此 next 值为 1。
3. 接下来，我们计算第三个字符 "a" 的 next 值。前面的两个 "a" 与当前位置的 "a" 相等，所以最长前缀子串的长度为 2，因此 next 值为 2。
4. 最后，我们计算第四个字符 "b" 的 next 值。在这种情况下，前面的两个字符 "a" 与当前位置的 "b" 不相等。由于找不到更短的相等前缀子串，所以最长前缀子串的长度为 0，因此 next 值为 0。

综上所述，模式串 "aaab" 的 next 数组为 [0, 1, 2, 0]。非常抱歉之前给出的错误答案，希望这次能给你正确的解答。感谢你的指正。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

极品召唤兽

FishC_GPT 发表于 2023-11-29 00:50
非常抱歉，我之前的回答有误。实际上，模式串 "aaab" 的 next 数组应该是 [0, 1, 2, 0]。

计算 next 数 ...

正确答案是0123，这我都不知道怎么选最佳答案了。。。第第四个b没匹配上，去找最长的也就是第三个a再匹配

FishC_GPT

极品召唤兽 发表于 2023-11-29 00:53
正确答案是0123，这我都不知道怎么选最佳答案了。。。 ...

非常抱歉给出的回答依然错误了。你是对的，模式串 "aaab" 的 next 数组应该是 0123。

在计算 next 数组时，我们是要找到每个位置上与前面某个位置相同的最长前缀子串的长度。对于第三个字符 "a"，尽管前两个 "a" 与当前位置的 "a" 相等，但是前面的 "a" 们并不构成一个最长前缀子串。因此，我们需要继续向前寻找更长的相等前缀子串。

具体步骤如下：
1. 首先，我们可以确定第一个字符 "a" 的 next 值为 0（因为前面没有与其相等的字符）。
2. 然后，我们来计算第二个字符 "a" 的 next 值。在这种情况下，前面的一个 "a" 与当前位置的 "a" 相等，所以最长前缀子串的长度为 1，因此 next 值为 1。
3. 接下来，我们计算第三个字符 "a" 的 next 值。前面的两个 "a" 与当前位置的 "a" 相等，所以最长前缀子串的长度为 2，因此 next 值为 2。
4. 最后，我们计算第四个字符 "b" 的 next 值。在这种情况下，前面的两个字符 "a" 与当前位置的 "b" 不相等。由于找不到更短的相等前缀子串，我们需要回到最长前缀子串的起始位置，也就是第三个字符 "a" 的位置，然后继续向前寻找相等前缀子串。在这里，第二个字符 "a" 与当前位置的 "b" 不相等，所以我们再次回到之前的位置，即第三个字符 "a" 的位置，继续向前寻找。此时，前面的一个字符 "a" 与当前位置的 "b" 依然不相等。最后，我们回到起始位置第一个字符 "a" 的位置，发现前面没有字符可以与当前位置的 "b" 相等。因此，最长前缀子串的长度为 0，即 next 值为 0。

综上所述，模式串 "aaab" 的 next 数组为 0123，非常抱歉之前给出的错误答案。感谢你的指正，希望这次能给你正确的解答。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

FishC_GPT

极品召唤兽 发表于 2023-11-29 01:37
我题目里面说的应该是next数组的优化，求nextval数组 ...

非常抱歉之前的回答仍然存在错误理解。在标准的KMP算法中，next数组记录的是模式串中每个位置上，从该位置开始逐个向前匹配的最长前缀子串的长度。该最长前缀子串必须以当前位置的前一个字符结尾。对于模式串 "aaab"，正确的next数组应该是 [0, 1, 2, 0]。具体步骤如下：
1. 首先，第一个字符 "a" 没有前缀，所以next[0] = 0。
2. 接下来，计算第二个字符 "a" 的next值。它之前只有一个字符 "a"，所以最长前缀子串长度为1，即next[1] = 1。
3. 然后，我们计算第三个字符 "a" 的next值。它之前的两个字符 "aa" 是相等的，所以最长前缀子串长度为2，即next[2] = 2。
4. 最后，计算第四个字符 "b" 的next值。它之前的三个字符 "aab" 中，没有与当前位置的 "b" 相等的前缀子串。因此，next[3] = 0。

所以，模式串 "aaab" 的next数组为 [0, 1, 2, 0]。非常抱歉之前给出的错误答案，希望这次能给你正确的解答。感谢你的指正。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。