kmp算法的基本思想
主串：a b a c a a b a c a b a c a b a a b b，下文中我们称作T模式串：a b a c a b，下文中我们称作W在暴力字符串匹配过程中，我们会从T[0] 跟 W[0] 匹配，如果相等则匹配下一个字符，直到出现不相等的情况，此时我们会简单的丢弃前面的匹配信息，然后从T[1] 跟 W[0]匹配，循环进行，直到主串结束，或者出现匹配的情况。这种简单的丢弃前面的匹配信息，造成了极大的浪费和低下的匹配效率。然而，在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。在第一次匹配过程中T: a b a c a a b a c a b a c a b a a b bW: a b a c ab在T[5]与W[5]出现了不匹配，而T[0]~T[4]是匹配的，现在T[0]~T[4]就是上文中说的已经匹配的模式串子串，现在移动找出最长的相同的前缀和后缀并使他们重叠：T: a b a c aab a c a b a c a b a a b bW: a b a c ab然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。然而，有些同学可能会问了，每次都要计算最长的相同的前缀会不会反而浪费了时间，对于模式串来说，我们会提前计算出每个匹配失败的位置应该移动的距离，花费的时间是常数时间。比如： j 012345W[j] a bacabF(j)00 1012当W[j]与T[i]不匹配的时候，设置j = F(j-1)文献中，朱洪对KMP算法作了修改，他修改了KMP算法中的next函数，即求next函数时不但要求W[1,next(j)-1]=W[j-(next(j)-1)，j-1]，而且要求W[next(j)]W[j]，他记修改后的next函数为newnext。显然在模式串字符重复高的情况下，朱洪的KMP算法比KMP算法更加有效。以下给出朱洪的改进KMP算法和next函数和newnext函数的计算算法。
算法-KMP
大一下参加学校ACM预备队集训的时候首次接触KMP算法，当时看了很多介绍文章，仍然不是很理解其实质，只是简单地套模板AC题目，待大二数据结构与算法课堂上再听老师介绍一次，才恍然大悟其实KMP也就是那么回事嘛。但当初为啥看那么多文章都没弄明白呢？正巧最近和朋友聊天时他告诉我他对KMP不是很理解，于是打算自己写一篇文章，巩固自己对KMP的认识，也希望能够帮助更多朋友理解KMP。 在开始之前，需要知晓的概念： 前缀：以原串串头为自身串头的子串，如 的前缀有： 后缀：以原串串尾为自身串尾的子串，如 的后缀有： 注意：字符串前后缀都不包括该串本身 给你一个文本串T(Text String) 再给你一个模式串P(Pattern String) 问该模式串是否在文本串中，怎么找？ 一开始只好分别从文本串与模式串的串头开始逐字母比较 二者相同，再比较T串与P串的下一位 如此反复 如果一直这么顺利，两串对应位置的字符总相同，待P串中最后一个字符也匹配完毕，说明该模式串在文本串中存在，耶( •̀ ω •́ )y超开心，查找结束。但，大多数匹配过程不会如此顺利，在该例中，当匹配进行至 很明显，失配了。现在怎么办？按朴素思想，将P串相对T串整体右移一位，重新开始匹配，即 但这种算法效率无疑是十分低下的。设T串长度N，P串长度M，则朴素算法时间复杂度为O(MN) 已知的重要信息并没有被使用——已匹配的字符串前缀 在上例中，当P串最后一个字符匹配失败时，其已有包含七个字符的 前缀子串S 匹配成功 完全可以利用前缀子串S做点什么。观察到在S串 中，有相同前后缀，即下图蓝色部分 而S串各字符又与T串中对应字符相同，即有 当失配发生后，直接将P串右移四位使S串蓝色后缀部分对齐T串中蓝色前缀部分 从图中红框部分继续尝试匹配，发现再次失配。这次，已匹配成功的前缀串S为 而在该串中没有相同的前后缀，只能将P串串头移至失配处进行比较 再次失配。此时前缀串S为空串，只好如朴素算法般将P串整体右移一位，重新开始比较 匹配成功。于是又按照之前的步骤往下匹配，直至再次失配或匹配成功 后续步骤同上，不再赘述 上述示例已展现，KMP算法的精髓在于对已匹配成功的前缀串S的利用 在朴素算法中，匹配失败了，T串待匹配字符会回溯 T串原本已匹配至T[7] = 'X'，但是因为失配，需回溯到T[1] = 'b'重新开始匹配 而在KMP算法中，若P[M]与T[K]匹配失败，K不会回溯。既然匹配过程是从T[0]开始逐渐向右进行的，至T[K]失配发生时，T[0]至T[K-1]早已匹配过，何必再回溯过去重复匹配呢？于是乎，就如问题引入部分展示般 每当失配发生，我们总是去关注P串中已匹配成功的前缀串S 因为该前缀串是匹配成功的，说明在T串中必定存在与该前缀串相同的子串，记为S' 若S串中存在相同前后缀 则S'串必然也存在此相同前后缀 所以只需将P串右移四位，使得S串的该相同前缀对齐S'串的该相同后缀 再尝试比较T[7]与P[3] 至于T[7]与P[3]是否能够匹配另说（当然，本例中一看就知道没匹配上），但通过对前缀串S的利用，成功省去了P串右移一位、两位和三位后的无效匹配 继续深入思考，给定一个具体的P串，其第N位的前缀串S内容是固定的，则S是否存在相同前后缀、相同前后缀的长度与内容也是确定的。换言之，对于一个具体的P串，当其与给定T串匹配至P[N]失配，P串应右移几位再次与T串进行匹配也是确定的。我们完全可以使用一个数组记录当P[N]失配后，应当使用N之前的哪一位再来与T串进行匹配，以此提高匹配效率，记该数组为Next数组 定义Next[i] = j表示当P串中第i位失配后，跳转至P串第j位再次尝试匹配 还是以之前的P串为例，它的Next数组求出来应为 取下标5为例，其前缀串为 最长相同前后缀为 若P[5]失配，应跳转至P[1]再次尝试匹配（最长相同前缀对应P[0]，则取其后一位P[1]，若存在多位，则取最后一位的下一位），P[5]的前一个字符P[4]对应字符'a'，而P[1]前一个字符P[0]同对应字符'a'，保证了P[1]之前字符与T串中对应字符保持匹配。所以Next[5] = 1，其余下标对应Next数组值同如此求。 特别地，规定Next[0] = -1。而对于除下标0外的任意下标N，Next[N]的含义是 前N-1个已匹配成功的字符构成的前缀串S中，最长相同前后缀长度。 所以若在下标为N处匹配失败了，则应前往Next[N]所对应的下标处匹配。 具体地，以下图所示为例，P[6]与T[6]失配 而Next[6] = 2，所以使用P[2]再次尝试与T[6]进行匹配 当求出P串Next数组后，便可快速进行与T串的匹配 现在问题只剩下如何求Next数组，注意到Next数组既然只与P串本身相关，与文本串T无关，故令P串与自身匹配即可求得 考虑字符串 其Next数组应为 令其与给定文本串相匹配 当匹配进行至 失配，于是跳转至P[Next[3]] = P[1]处再次尝试匹配 再度失配，也必然失配 问题在于不该出现P[N] =P[Next[N]] 若P[N] =P[Next[N]]，则P[N]失配后使用P[Next[N]]再次尝试匹配，由于P[N] =P[Next[N]]，P[N]匹配失败，P[Next[N]]必然也失败 因此，若出现P[N] =P[Next[N]]情况，则令Next[N]=Next[Next[N]] 本例中该字符串新Next数组为 当匹配进行至 失配，于是跳转至P[Next[3]] = P[0]处再次尝试匹配 省去了之前跳转至P[1]处的无效匹配 设T串长度M，P串长度N，由于KMP算法不会回溯，分析易知时间复杂度为O(m+n) 对于P[N]，若其前缀串S含相同前后缀F，且F长度为n（n>1），Next[N]可以取1至n中任意值，为最大化匹配效率考虑，总是取最大相同前后缀以提高效率，节省时间
求KMP算法 基本思想
(1)求得模式串中每个字符的next[j]值；
(2)进行模式匹配。
假设i和j分别为指示主串和模式串中正在比较的字符的当前位置，并对i 和j 赋初值0。在匹配的过程中，若si=tj，则i和j分别增加1，继续进行比较，否则，i不变，而j退回到next[j]的位置进行新一轮的比较。如此递推下去，直到出现下列两种情况：
当j退回到某个值next[j]值时，匹配成功，则i和j分别增加1继续匹配；
当j退回到值为0时，即next[j]=0，说明主串的当前字符匹配失败，这时将主串向右滑动一个位置，即从i+1处重新开始新一轮的匹配，此时j=0。
关于KMP算法的说明有什么？
（1）未改进的模式匹配算法的时间复杂度为O（nm），但在一般情况下，其实际的执行时间接近O（n＋m），因此至今仍被采用。（2）KMP算法仅当模式与主串之间存在许多“部分”匹配的情况下才显得比未改进的模式匹配快。（2）KMP算法的最大特点是指示主串的指针不需要回溯，在整个匹配过程中，对主串仅需要从头至尾扫描一遍，这对处理存储在外存上的大文件是非常有效的。
