KMP算法考题 - 图文

KMP算法是在最近这两年的软件设计师考试中才出现的。2次都是让求Next函数的序列（其实是）。先看看题吧。 （2011年下半年上午题）

（2012年上半年上午题）

其实做这个题很简单，我先说说这个题里的各种概念。

给定的字符串叫做模式串T。j表示next函数的参数，其值是从1到n。而k则表示一种情况下的next函数值。p表示其中的某个字符，下标从1开始。看等式左右对应的字符是否相等。 好了，开始做题了。

首先，要把字符串填入到一个表格中：（拿第一个题为例）

将j导入next函数，即可求得，

j=1时，next[0]=0；

j=2时，k的取值为(1,j)的开区间，所以整数k是不存在的，那就是第三种情况，next[2]=1；

j=3时，k的取值为（1，3）的开区间，k从最大的开始取值，然后带入含p的式子中验证等式是否成立，不成立k取第二大的值。现在是k=2，将k导入p的式子中得，p1=p2，即“a”=“b”，显然不成立，

舍去。k再取值就超出范围了，所以next[3]不属于第二种情况，那就是第三种了，即next[3]=1；

j=4时，k的取值为（1，4）的开区间，先取k=3，将k导入p的式子中得，p1p2=p2p3，不成立。 再取k=2，得p1=p3，成立。所以next[4]=2；

j=5时，k的取值为（1，5）的开区间，先取k=4，将k导入p的式子中得，p1p2p3=p2p3p4，不成立。 再取k=2，得p1p2=p3p4，不成立。 再取k=2，得p1=p4，成立。所以next[4]=2；

j=6时，k的取值为（1，6）的开区间，先取k=5，将k导入p的式子中得，p1p2p3p4=p2p3p4p5，不成立。 取k=4，得p1p2p3=p3p4p5，不成立。再取k=3，将k导入p的式子中得，p1p2=p4p5，成立。所以next[4]=3；

j=7时，k的取值为（1，7）的开区间，先取k=6，将k导入p的式子中得，p1p2p3p4p5=p2p3p4p5p6，不成立。 再取k=5，得 p1p2p3p4=p3p4p5p6 ，不成立。 再取k=4，得 p1p2p3=p4p5p6 ，成立。所以next[4]=4；

j=8时，k的取值为（1，8）的开区间， 先取k=7，将k导入p的式子中得，p1p2p3p4p5p6=p2p3p4p5p6p7，不成立。 再取k=6，得p1p2p3p4p5=p3p4p5p6p7，不成立。 再取k=5，得

p1p2p3p4=p4p5p6p7，不成立。 再取k=4，得p1p2p3=p5p6p7，不成立。 再取k=3，得p1p2=p6p7，不成立。再取k=2，得p1=p7，不成立。k再取值就超出范围了，所以next[3]不属于第二种情况，那就是第三种了，即next[3]=1；

所以结果为：