关于#数据结构#的问题，请各位专家解答！（相关搜索：next数组）

Question

这个的next计算为什么第一位为-1呢，为什么选择B而不是A，有的文章说第一位一定为-1，有的说第一位和第二位一定是0和1，到底是哪个，这个例子按照这个算法

除去第一位为-1之外我算选A啊，而下一个例子

按照第二图算法，算第三图，是选择C是对的，这个我懂了，但是这俩个例子在我这特别矛盾。

图一与图三的算法有什么不同呢，第二图求next数组的方法是正确的吗？

Answer 1

【以下回答由 GPT 生成】

对于计算next数组的算法，可以使用如下步骤：

1. 定义一个长度为n的next数组，初始值都为0。
2. 对于字符串s，从下标1开始，依次计算每个位置的next值。
3. 遍历字符串s中的每个位置i，计算其对应的next值。

具体的计算规则如下：

• 如果i为0，则将next[i]赋值为-1。
• 否则，将j初始化为next[i-1]的值。
• 如果s[i]等于s[j]，则将next[i]的值设置为j+1。
• 如果s[i]不等于s[j]，则将j更新为next[j]的值，并重复该步骤，直到s[i]等于s[j]或者j为-1。

通过以上步骤，即可计算出完整的next数组。

回到问题的具体情况，图一和图三中给出了两种不同计算next数组的方法。对比两种方法，发现有以下不同之处：

1. 图一中的算法中，第一个元素的next值为-1，而图三的算法中第一个元素的next值为0。
2. 图一中的算法中，第二个元素的next值为0，而图三的算法中第二个元素的next值为1。

根据一般算法的理解，第一个元素的next值应为0，而第二个元素的next值应为1。因此，可以认为图三给出的计算方法是更为常见和正确的。

综上所述，图一与图三的算法有明显的不同之处，其中图三给出的计算方法更为常见和正确。

如果你有其他相关问题，请随时提问。

【相关推荐】

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/732377
• 除此之外, 这篇博客: C语言程序设计--配套书（第三版）中的 7.6有两个运动队a和b, 各有10个队员，每个队员有一个综合成绩，将两个队的每个队员是我成绩按顺序–对应地逐个比较（即a队第一个队员与b队第一个队员比,…)如果a队队员的成绩高于b队相应队员成绩的数目多于队相应队员成绩的数目（例如：a队赢6次，b队赢4次），则认为a获胜，统计出两队队员比较的结果（a队高于，等于，低于b队） 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^