今天，在看数据结构--串这一章节时，看到了kmp算法，相对较复杂些，在此单独做下整理。
kmp算法是一种改进的字符串匹配算法，由d.e.knuth与v.r.pratt和j.h.morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称kmp算法）。kmp算法的关键是根据给定的模式串w1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息。
例子：
假如我们要比较两个字符串是否相等。
在t串中查找s串。我们用最笨的方法去想，就是将t串与s串中的每一个元素一一去匹配，
如图所示，一旦s串中的一个元素与t串中的元素不匹配，则在t串中向后移动一个位置，再重头进行比较。
通过上图可以想象，最糟糕的情况就是都匹配不到，这样的匹配方式性能很低。
后来我们的前辈们，发现了kmp算法，下面我们来看图。
根据这种思想，可以得出如图步骤
再看一个例子
是否将s串的首字符直接移动到第六个字符呢？
首先，我们先来分析下s串。按照上面图三，
第一步我们先确认s串本身相同的字符，
前三个字符a<>b<>c，
第1、2字符a b 与 第3、4字符a b相等。
第3个字符c与第6个字符x不相等。
第二步，根据第一步结论，看下图，途中我加了坐标，
因为s1 <> s2 <> s3 并且 s1=t1、s2=t2、s3=t3、s4=t4、s5=t5。
所以s1 s2不需要再和t2 t3 t4 t5进行比较（因为你已经知道了，谁和谁是否相等）
s6 <> t6 并且s3 <> s6，所以要比较s3 是否等于 t6，所以就会有下图。
所以no2，应该移动到如上图所示的位置，到此kmp的算法思想就是这样，需要好好领会下。
总结设计思想，我认首先对匹配字符串本身相同字符进行一个记录、其次利用t与s串匹配过的记录进行判断，避免再进行多余的匹配操作。
下面再说下，如果记录匹配字符串本本身相同的字符统计，在数据结构书里叫做next数值推导（根据推导出的每个字符下的数值，当匹配时，此数值不等于被匹配的字符串字符时，按照此数值下的next值，进行位置的移动）
next推导公式：相似字符个数 + 1