KMP 算法
在简单的字符串匹配算法中我们一般会使用这样的匹配demo去做处理,返回子串T在主串S，pos之后的位置,这里子串在主串中重复的情况。
int Index(SSTring S,SSTring T, int pos) {
if (!S || !T) return
if (!(pos >=0 && pos < S.length)) return
int i = pos; j = 0;
while(i < S.lenth && j < T.length) {
if (S[i] == T[j]) j++;
else j = 0;
i++;
}
if (j > T.length) return i - T.length;
else return 0;
}这就是我们在想字符串匹配的时候，会第一个想起来的算法。当我们哪一个子串去匹配一个主串的时候，首先看字符串是否相等，当字符串不相等时，将主串向后移动一个位置，同时将子串的匹配部分直接指到子串的第一个位置。当字符串相等的时候，将子串和主串同时向后移动一个位置，在做匹配。
这里举两个例子：
// 主串S
afheiahiehiahdsifhaiefhiadshifhaueufaudsfaeaklkfghjkl
// 子串
kfghjkl在这种情况下的算法复杂度是O(m+n),m和n分别是子串和主串的长度。算法效率上还是比较能保障的。
但是如果在这样的例子中的话，算法的复杂度就变成了O(m*n),时间消耗就会大大的增加。
// 主串S
00000000000000000000000000000000000000001
// 子串
000000001你可能会说，我只是做一个简单的字符串的对比，没必要在算法上要求那么高。但是如果有一天，你被分配了一个处理文本编辑器的工作，你会不会想着优化一下用户在文本编辑器中的搜索速度。这个时候一个优秀的算法设计就显得格外的重要。
科学的发展总是迅速的，总有人会去将人类进化史上的坎坷磨平。在这样的背景之下，KMP（Knuth-Morris-Pratt算法）算法应运而生。下面我们就来了解一下KMP算法。
这里我们定义主串BBCABCDABABCDABCDABDE子串 ABCDABD
那么比较这个子串，就会出现
BBCABCDABABCDABCDABDE
|
ABCDABD首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。
BBCABCDABABCDABCDABDE
|
ABCDABD因为B与A不匹配，搜索词再往后移。
BBCABCDABABCDABCDABDE
|
ABCDABD就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。接着比较字符串和搜索词的下一个字符，还是相同。
BBCABCDABABCDABCDABDE
|
ABCDABD直到字符串有一个字符，与搜索词对应的字符不相同为止。
BBCABCDABABCDABCDABDE
|
ABCDABD这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把”搜索位置”移到已经比较过的位置，重比一遍。
一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。
索引 1 2 3 4 5 6 7
搜索串 A B C D A B D
匹配值 0 0 0 0 1 2 0阮一峰博客中给出了一个很好偶的解释，但是感觉还是有点问题，仅做参考。”部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例
"A"的前缀和后缀都为空集，共有元素的长度为0；
"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。这就是KMP算法的核心所在，根据子串中的匹配值来减少字符匹配的时间复杂度。
移动位数 = 已匹配的字符数 - 对应的部分匹配值得知了KMP字串中的匹配值，在得知A与D不匹配时
BBCABCDABABCDABCDABDE
|
ABCDABD利用字串中的信息，子串匹配到了第6位，第六位的匹配值位2，6-4=2，则只要将子串向后移动4位即可，记得到下面的样式
BBCABCDABABCDABCDABDE
|
ABCDABD这个时候的A和C也是不匹配的，所以重复上面的操作，可以得到2-0=2，子串再次向后移动2位
BBCABCDABABCDABCDABDE
|
ABCDABD重复上面的操作，知道找到对应的匹配为止
BBCABCDABABCDABCDABDE
|
ABCDABD