next数组

已知串S=′aaab′,其Next数组值为()

正确答案: A

0123

1123

1231

1211

next数组的求解方法是：第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。

对于本题，求next值的过程：

前两位：next数组值前两位一定为01，即aaab中的前两位aa对应01，如上表中next第1，2位为0和1.其实这就可以选出答案了.第三位：3a前面是2a（2a表示序号为2的a），2a的next数组值为1，将2a和1a相比，两者相同，都是a，则3a的next值为2a的next值加1，即2；第四位：4b前3a的next为2，3a与2a相比，二者相同，则其next值为2a的next加1，为3.结果为0123，选A如果比较的时候碰到与前一位字符“不同”怎么办？那就以前一位的next值为序号，找到这个序号对应的字符，再进行比较，如果与之相同，就用这一位的next值+1，如果不同就继续重复这个操作直到找到相同的字符为止。如果一直重复到第一位还找不到，则将所求位的next值置为1。