数据结构-KMP形式匹配算法
今天，在看数据结构--串这一章节时，看到了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