next数组详解

 

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

看起来很费解，然后结合下面例子具体运算一遍。

求模式串 a b a a a b c a a c 

1、next数组前两位必定为01，即

a  b  a  a  a  b  c  a  a  c 

1 2  3  4  5  6  7  8  9 10

0 1

2、计算第3位时，看第2位的next值为1，则把b和1对应的a进行比较，不同，则第3位a的next值为1，因为一直比到最前一位，都没有发生比较相同的现象。

a  b  a  a  a  b  c  a  a  c 

1 2  3  4  5  6  7  8  9 10

0 1  1

3、计算第4位的时候，看第3位a的next值为1，则把a和1对应的a进行比较，相同，则第4位a的next的值为第3位a的next值加上1，为2。因为是在第3位实现了其next值对应的值与第3位的值相同。

a  b  a  a  a  b  c  a  a  c 

1 2  3  4  5  6  7  8  9 10

0 1  1  2

4、计算第5位的时候，看第4位a的next值为2，则把a和2对应的b进行比较，不同，再将b对应的next值1对应的a与第4位的a进行比较，相同。则第5位的next值为第2位b的next值加上1，为2。因为是在第2位实现了其next值对应的值与第4位的值相同。

a  b  a  a  a  b  c  a  a  c 

1 2  3  4  5  6  7  8  9 10

0 1  1  2  2

5、计算第6位的时候，看第5位a的next值为2，则把a和2对应的b进行比较，不同，则再将b对应的next值1对应的a与第5位的a进行比较，相同，则第6位的next值为第2位b的next值加上1，为2。因为是在第2位实现了其next值对应的值与第5位的值相同。

a  b  a  a  a  b  c  a  a  c 

1 2  3  4  5  6  7  8  9 10

0 1  1  2  2  2

6、计算第7位的时候，看第6位b的next值为2，则把b和2对应的b进行比较，相同，则第7位c的next值为第6位b的next值加上1，为3，因为是在第6位实现了其next值对应的值与第6位相同。

a  b  a  a  a  b  c  a  a  c 

1 2  3  4  5  6  7  8  9 10

0 1  1  2  2  2  3

7、计算第8位的时候，看第7位c的next值为3，则把c和3对应的a进行比较，不同，则再把第3位a的next值1对应的a与第7位c比较，仍然不同，则第8位的next值为1。

a  b  a  a  a  b  c  a  a  c 

1 2  3  4  5  6  7  8  9 10

0 1  1  2  2  2  3  1  

8、计算第9位的时候，看第8位a的next值为1，则把a与1对应的a比较，相同，则第9位a的next值为第8位a的next值加1，为2。因为是在第8位实现了其next值对应的值与第8位相同。

a  b  a  a  a  b  c  a  a  c 

1 2  3  4  5  6  7  8  9 10

0 1  1  2  2  2  3  1  2

9、计算第10位的时候，看第9位a的next值为2，则把a和2对应的b进行比较，不同，则再把第2位b的next值1对应的a与第9位a比较，相同，则第9位a的next值为第2为b的next值加1，为2。因为是在第2位实现了其next值对应的值与第9位的值相同。

a  b  a  a  a  b  c  a  a  c 

1 2  3  4  5  6  7  8  9 10

0 1  1  2  2  2  3  1  2   2