KMP算法next计算

你的名字 2022-06-08 04:07 235阅读 0赞

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

（2011年下半年上午题）

![1351950256_4566.png][]

（2012年上半年上午题）

![1351950280_5613.png][]

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

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

好了，开始做题了。

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

![Image 1][]

![1351950307_3232.png][]

将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**；

所以结果为：

![Image 1][]

![1351950969_9261.png][]

好了，第二题留给大家做吧。

转自 [http://blog.csdn.net/xiaoxian8023/article/details/8134292][http_blog.csdn.net_xiaoxian8023_article_details_8134292]

[1351950256_4566.png]: https://img-my.csdn.net/uploads/201211/03/1351950256_4566.png
[1351950280_5613.png]: https://img-my.csdn.net/uploads/201211/03/1351950280_5613.png
[Image 1]: 
[1351950307_3232.png]: https://img-my.csdn.net/uploads/201211/03/1351950307_3232.png
[1351950969_9261.png]: https://img-my.csdn.net/uploads/201211/03/1351950969_9261.png
[http_blog.csdn.net_xiaoxian8023_article_details_8134292]: http://blog.csdn.net/xiaoxian8023/article/details/8134292