本文的理解建立在此 v_JULY_v 以及 阮一峰 的详解之上

本文是对 数据结构–C语言版 书中代码的详解与个人理解

上一节我只讲述了一下代码层面的理解，如果有算法背景不了解的可以去开篇的两篇教程中寻找答案。这里只阐述自己对于算法中较为难以理解部分的想法。

为了能清晰的讲述KMP总共大概花费了一礼拜的时间; 这里我将书上的failure数组称为next数组以节省篇幅; s代表代求解字符串，p代表模式字符串

这一段代码我认为是我个人最难以理解的。

    i = failure[i];

首先这里的背景是，在求next数组某一循环时发现p[j]!=p[i+1],且i>=0。换言之p₀,p₁, … p_i != p_j-1, p_j-i+1, …p_j，因此我希望能够在p₀,p₁, … p_i中找到一个位置x(x < p)，使得p₀,p₁,…p_x = p_j-x, p_j-x+1,…p_j。

简而言之，就是希望能够找到一条稍微短一些的公共缀。可以参考v_JULY_v教程里的图

而算法的答案是：你可以试试x = next[i]，说不定可行。注意，这里x = next[i]不是一次就可以找到，因此也就是while存在的价值。

难点依然存在，为什么x = next[i]就可以快速的找到这个x呢？这也是我这么多天一直困扰的地方。

    while(pat[j] != pat[i+1] && i>0)
        i = failure[i];

总结了一下，其实难点在于几个指针的意义不明确。这里j很好理解，指向当前需要求解的位置，i才是重点。

注意，这里的指针概念全部都引用自KMP心得-1里的代码实现

1. next[i]代表了前缀末尾的下标
2. next[i]+1代表了前后缀的长度
3. next[i]代表了字符s[i]可回溯到的下标

这里我用一句话概括求解next数组的中心思想：让模式串p与自身匹配

知晓了此中心思想，理解算法就游刃有余了。

假定现在已知模式串为，我将结果和序号一一标示在下边

0	1	2	3	4	5	6	7
A	B	A	C	A	B	A	B
-1	-1	0	-1	0	1	2	？

此时i=2（i=next[j-1]），为求解B的next值，根据算法比对前缀ABAC与后缀ABAB（pat[j]!=pat[i]，B!=C），不匹配，这个时候就是关键点了。

直接从字面上寻找，当然很快就能找到s[1] = s[7]的事实，也就是next[7] = 1。

如果这个过程改为p于自身匹配，这个时候就很好理解了。

A B A C A B A B

- - - - A B A C A B A B

模拟pmatch的过程，现前循环是这样的。发现B!=C，此时不是从头开始再次匹配，而是回溯到某一个位置重新比对，也就是next[i]（next[2]=0），这就是为什么i可以通过赋值next[i]来迭代寻找的核心原因!

A B A C A B A B

- - - - - - A B A C A B A B

此时s[7]==p[1]，next[7]=1!因为谁也不能保证p[next[i]]=p[j]，因此这里用while循环。其实和pmatch里的while是一个道理，我并不清楚回溯之后string[i]和pat[j]是否相等，所以while里j的值一直迭代。

总结一下，其实求解next数组受益于求解前后缀，其实质就是在匹配自身字符串，大致的核心思想都是相同的。