字符串kmp算法
㈠ 数据结构与算法——字符串匹配问题(KMP算法)
KMP算法也是比较着名的模式匹配算法。是由 D.E.Knuth,J.H.Morrs 和 VR.Pratt 发表的一个模式匹配算法。可以大大避免重复遍历的情况。
如果使用暴风算法的话，前面五个字母完全相等，直到第六个字母 "f" 和 "x" 不相等。如下图：
T = “abcdex”
j 123456
模式串 abcdex
next[j] 011111
T = "abcabx"
j 123456
模式串T abcabx
next[j] 011123
T = "ababaaaba"
j———————123456789
模式串T——— ababaaaba
next[j]————011234223
T = "aaaaaaaab"
j———————123456789
模式串T——— aaaaaaaab
next[j]————012345678
next数组其实就是求解字符串要回溯的位置
假设，主串S= “abcababca”;模式串T=“abcdex”，由以上分析得出next数组为011111，next数组意味着当主串与模式串不匹配时，都需要从第一个的位置重新比较。
KMP算法也是有缺陷的，比如主串S=“aaaabcde”,模式串T= “aaaaax”。next的数组就是012345；
当开始匹配时，当i= 5，j = 5时，我们发现字符"b"与字符“a”不相等，如上图，j = next[5] = 4;
由于T串的第二、三、四、五位置的字符都与首位“a”相等，那么可以用首位next[1]的值去取代与它相等的后续字符的next[j],那么next数组为{0,0,0,0,0,5};
在求解nextVal数组的5种情况
㈡ 算法-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字符串匹配算法
kmp算法跟之前讲的bm算法思想有一定的相似性。之前提到过，bm算法中有个好后缀的概念，而在kmp中有个好前缀的概念，什么是好前缀，我们先来看下面这个例子。
观察上面这个例子，已经匹配的abcde称为好前缀，a与之后的bcde都不匹配，所以没有必要再比一次，直接滑动到e之后即可。
那如果前缀中有互相匹配的字符呢？
观察上面这个例子，这个时候如果我们直接滑到好前缀之后，则会过度滑动，错失匹配子串。那我们如何根据好前缀来进行合理滑动？
其实就是看当前的好前缀的前缀和后缀是否有匹配的，找到最长匹配长度，直接滑动。鉴于不止一次找最长匹配长度，我们完全可以先初始化一个数组，保存在当前好前缀情况下，最长匹配长度是多少，这时候我们的next数组就出来了。
我们定义一个next数组，表示在当前好前缀下，好前缀的前缀和后缀的最长匹配子串长度，这个最长匹配长度表示这个子串之前已经匹配过匹配了，不需要再次进行匹配，直接从子串的下一个字符开始匹配。
我们是否每次算next[i]时都需要每一个字符进行匹配，是否可以根据next[i - 1]进行推导以便减少不必要的比较。
带着这个思路我们来看看下面的步骤：
假设next[i - 1] = k - 1;
如果modelStr[k] = modelStr[i] 则next[i]=k
如果modelStr[k] != modelStr[i]，我们是否可以直接认定next[i] = next[i - 1]？
通过上面这个例子，我们可以很清晰地看到，next[i]!=next[i-1]，那当modelStr[k]!=modelStr[i]时候，我们已知next[0],next[1]…next[i-1]，如何推导出next[i]呢？
假设modelStr[x…i]是前缀后缀能匹配的最长后缀子串，那么最长匹配前缀子串为modelStr[0…i-x]
我们在求这个最长匹配串的时候，他的前面的次长匹配串（不包含当前i的），也就是modelStr[x…i-1]在之前应该是已经求解出来了的，因此我们只需要找到这个某一个已经求解的匹配串，假设前缀子串为modelStr[0…i-x-1],后缀子串为modelStr[x…i-1],且modelStr[i-x] == modelStr[i],这个前缀后缀子串即为次前缀子串，加上当前字符即为最长匹配前缀后缀子串。
代码实现
首先在kmp算法中最主要的next数组，这个数组标志着截止到当前下标的最长前缀后缀匹配子串字符个数，kmp算法里面，如果某个前缀是好前缀，即与模式串前缀匹配，我们就可以利用一定的技巧不止向前滑动一个字符，具体看前面的讲解。我们提前不知道哪些是好前缀，并且匹配过程不止一次，因此我们在最开始调用一个初始化方法，初始化next数组。
1.如果上一个字符的最长前缀子串的下一个字符==当前字符，上一个字符的最长前缀子串直接加上当前字符即可
2.如果不等于，需要找到之前存在的最长前缀子串的下一个字符等于当前子串的，然后设置当前字符子串的最长前缀后缀子串
然后开始利用next数组进行匹配，从第一个字符开始匹配进行匹配，找到第一个不匹配的字符，这时候之前的都是匹配的，接下来先判断是否已经是完全匹配，是直接返回，不是，判断是否第一个就不匹配，是直接往后面匹配。如果有好前缀，这时候就利用到了next数组，通过next数组知道当前可以从哪个开始匹配，之前的都不用进行匹配。
㈣ KMP算法求next数组的问题
字符串如果是以0为下标的话next[7]是0，只有最后一位与第一位相等。
在第i个字符前面的i-1个字符里面，
从开头开始的1个字符与最后1个字符是否相等，若不是，则next[i]=0；
从开头开始的2个字符与最后2个字符是否相等，若不是，则next[i]=1；
从开头开始的3个字符与最后3个字符是否相等，若不是，则next[i]=2；
前缀next数组的求解算法：
void SetPrefix(const char *Pattern, int prefix[])
{
int len=CharLen(Pattern);//模式字符串长度。
prefix[0]=0;
for(int i=1; i<len; i++)
{
int k=prefix[i-1];
//不断递归判断是否存在子对称，k=0说明不再有子对称，Pattern[i] != Pattern[k]说明虽然对称，但是对称后面的值和当前的字符值不相等，所以继续递推。
(4)字符串kmp算法扩展阅读：
kmp算法完成的任务是：给定两个字符串O和f，长度分别为n和m，判断f是否在O中出现，如果出现则返回出现的位置。常规方法是遍历a的每一个位置，然后从该位置开始和b进行匹配，但是这种方法的复杂度是O(nm)。kmp算法通过一个O(m)的预处理，使匹配的复杂度降为O(n+m)。
㈤ 解析一哈c语言中的kmp算法，bf算法,kr算法之间的联系与区别，尽量浅显易懂，谢谢！
三种算法联系：都是字符串匹配算法。
区别：
“KMP算法”：在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。
“BF算法”是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配，若相等，则继续比较S的第二个字符和P的第二个字符；若不相等，则比较S的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果。
“KR算法”在每次比较时，用HASH算法计算文本串和模式串的HASH映射，通过比较映射值的大小来比较字符串是否匹配。但是考虑到HASH冲突，所以在映射值相同的时候，还需要近一步比较字符串是否相同。但是在每次比较时，需要计算HASH值，所以选择合适的HASH算法很重要。
略知一二！
㈥ 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
b
W:
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
b
W:
a
b
a
c
ab
然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。
然而，有些同学可能会问了，每次都要计算最长的相同的前缀会不会反而浪费了时间，对于模式串来说，我们会提前计算出每个匹配失败的位置应该移动的距离，花费的时间是常数时间。比如：
j012345W[j]abacabF(j)001012当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函数的计算算法。