实现KMP字符串匹配,函数kmp实现串的模式匹配
个人认为这篇文章是关于KMP算法的在线介绍，比较容易理解。真的很“详细”，耐心看完一定会有所收获~ ~。另外，模式函数next[i]的值有很多版本，在其他面向对象的算法描述中也有失效函数f(j)的说法，实际上就是next[j]=F (J)。
KMP字符串模式匹配的详细说明
KMP字符串模式匹配是在一个字符串中定位另一个字符串的有效算法。简单匹配算法的时间复杂度为O(m * n)；KMP匹配算法。可以证明其时间复杂度为O(m ^ n)。
1.简单匹配算法
让我们首先来看一个简单匹配算法的功能：
int Index_BF ( char S [ ]，char T [ ]，int pos)
/*如果字符串s从第一个pos(s的下标0pos strlength(s))字符开始
如果有一个子串与字符串T相同，则匹配成功，返回第一个。
字符串S中此类子字符串的下标，否则为-1 */
int i=pos，j=0；
while ( S[i j]！=/0 T[j]！=/0)
if ( S[i j]==T[j])
j；//继续比较最后一个字符
其他
我；j=0；//重新开始新一轮匹配
if ( T[j]==/0 )
返回I；//匹配成功返回下标
其他
return-1；//字符串S中没有与字符串T相同的子字符串(来自pos字符)
} //索引_BF
这个算法的思想很简单：将主字符串S中从位置I开始的子字符串与模式字符串T进行比较，即从j=0开始比较S[i j]和T[j]。如果相等，则主串s中以I为起始位置有匹配成功的可能，继续向后比较(J逐渐递增1)直到等于T串中的最后一个字符。否则，从S字符串中的下一个字符开始下一轮‘匹配’，即字符串T向后滑动一位，即I增加1。
比如：在字符串s=" abcabdabba "中寻找t=" abcabd "(我们可以假设从下标0开始):首先比较S[0]和T[0]是否相等，然后比较S[1]和T[1]是否相等……我们发现直到比较S[5]和T[5]才相等。如图所示：
当出现这样的错配时，必须将T下标追溯到开头，S下标追溯的长度与T相同，然后将S下标加1，再进行比较。如图所示：
这一次，错配马上发生，T下标回到开头，S下标加1，然后再进行比较。如图所示：
这一次，错配马上发生，T下标回到开头，S下标加1，然后再进行比较。如图所示：
再次出现错配，于是T下标回到开头，S下标加1，然后再比较。T中的所有字符这次都匹配S中的对应字符。该函数返回s中t的起始下标3，如图所示：
2.KMP匹配算法
还是那个例子。在s=" ABCABDABBA "中查找t=" ABCABDABBA "。如果使用KMP匹配算法，在S[5]和T[5]不相同的第一个搜索结果后，S下标不追溯到1，T下标不追溯到开始，而是根据T(next[la ter])中t [5]= d 的模函数值，直接比较S[5]和T[2]是否相等，因为相等，所以S和T的下标同时增加；因为它们相等，所以s和t的下标同时增加。最后在s中找到了T，如图：
比较KMP匹配算法与简单匹配算法的效率，一个极端的例子是：
在S="AAAAAA … AAB" (100个A)中查找T="AAAAAAAAAB "。简单匹配算法总是比较T的结尾，并找到不同的字符。然后T的下标回到开头，S的下标也回到同样的长度然后加1。继续对比。如果使用KMP匹配算法，就不需要回溯。
对于一般文稿中的字符串匹配，简单匹配算法的时间复杂度可以降低到O (m n)，因此在大多数实际应用中得到应用。
KMP算法的核心思想是利用获得的部分匹配信息进行后续的匹配过程。看前面的例子。为什么t [5]= d 的模式函数值等于2(next[5]=2)？实际上，这个2意味着t [5]= d 前面有两个字符与前两个字符相同，t [5]= d 不等于前两个字符之后的第三个字符(t [2
也就是说，如果前两个字符之后的第三个字符也是 d ，那么t [5]= d 的模式函数值就不是2，而是0，即使T[5]= d 之前的两个字符与前两个字符相同。
我前面说过：在s=" ABCABDABBA "中寻找t=" ABCABDABBA "。如果使用KMP匹配算法，在第一次搜索到S[5]和T[5]不同的结果后，S下标不追溯到1，T下标不追溯到开始，而是直接根据t [5]= d 的模式函数值来比较S。为什么会这样？
刚才我说，“(next[5]=2)，其实这个2是指t [5]= d 前面有两个字符和前两个字符一样”。请看图：因为，S[4]==T[4]，S[3]==T[3]，根据next[5]=2，有T[3]==T[0]，T[4]==T[1]，所以S[3]=。
可能有人会问：S[3]和T[0]，S[4]和T[1]根据next[5]=2是间接相等的，那么S[1]和T[0]，S[2]和T[0]没有比较怎么能跳过呢？因为S[0]=T[0]，S[1]=T[1]，S[2]=T[2]，T[0]！=T[1]，T[1]！=T[2]，==S[0]！=S[1]，S[1]！=S[2]，所以S[1]！=T[0]，S[2]！=T[0]。理论上还是间接比较。
又有人问了。你是在分析特殊情况吗？
假设s是常数，那么在s中搜索t="ABA Abd "呢？答：这种情况下，当你比较S[2]和T[2]发现不相等时，就看next[2]的值。next[2]=-1，表示S[2]已经和T[0]间接比较过，不相等。接下来我们比较一下S[3]和T[0]。
假设S是常数，那么在S中搜索t="abbabd "呢？回答：在这种情况下，当比较S[2]和T[2]时，我们发现它们不相等。我们来看看next的值[2]。next[2]=0，表示S[2]已经和t[2]比较过，不相等。接下来我们比较一下S[2]和T[0]。
假设s="abaabcabadabba "在s中搜索t="abaabd "？回答：在这种情况下，当比较S[5]和T[5]时，我们发现它们不相等。我们来看看next[5]的值。next[5]=2，表示已经比较了前一个。其中，S[5]前面有两个字符，T的前两个相等。接下来我们比较一下S[5]和T[2]。
简而言之，有了字符串的下一个值，一切都完成了。那么，如何找到字符串下[n]个的模式函数值呢？(在本文中，next值、mode函数值和mode值是一个意思。)
3.如何找到字符串下一个[n]的模式值
(1)next[0]=-1含义：任意字符串第一个字符的众数值指定为-1。
(2)next[j]=-1含义：模式串T中带下标j的字符，如果与第一个字符相同
相同，J的前1-k个字符与前1-k个字符相同。
字符不相等(或相等但T[k]==T[j])(1k j)。
如果T=“ABC acad”，那么next[6]=-1，因为T[3]=T[6]
(3)next[j]=k含义：模式串T中带下标j的字符，如果j的第一个k
等于前k个字符，而T[j]！=T[k] (1k j).
那就是T[0]T[1]T[2]。T[k-1]==
T[j-k]T[j-k 1]T[j-k 2]…T[j-1]
还有T[j]！=T[k]。(1k j)；
(4) next[j]=0含义：除(1)、(2)、(3)以外的其他情况。
01)用t="abcac "求模式函数的值。
根据(1)，Next[0]=-1
接下来[1]=0根据(4)因为(3)有1=k不能说，j=1，T[j-1]==T[0]
下一个[2]=0根据(4)因为(3)有1=k (T[0]=a)！=(T[1]=b)
根据(2)，Next[3]=-1
根据(3)T[0]=T[3]和T[1]=T[4]，Next[4]=1
也就是
为什么T[0]==T[3]时还有next[4]=0？因为T[1]==T[4]，根据(3)”和T[j]！=T[k]”归类为(4)。
02)来个复杂点的，求t="ababc aabc "的mode函数值。
根据(1)，Next[0]=-1
根据(4)，Next[1]=0
根据(2)，Next[2]=-1
接下来[3]=0根据(3)，虽然T[0]=T[2]，T[1]=T[3]被归入(4)
Next[4]=2根据(3) T[0]T[1]=T[2]T[3]和T[2]！=T[4]
根据(2)，Next[5]=-1
Next[6]=1根据(3) T[0]=T[5]和T[1]！=T[6]
接下来[7]=0根据(3)，虽然T[0]=T[6]，T[1]=T[7]被归入(4)
Next[8]=2根据(3) T[0]T[1]=T[6]T[7]和T[2]！=T[8]
也就是
只要我们明白了next[3]=0而不是=1，next[6]=1而不是=-1，next[8]=2而不是=0，其他的一切似乎就好理解了。
03)让我们来一个特别的。求t="abcacad "的mode函数值。
Next[5]=0根据(3)，虽然T[0]T[1]=T[3]T[4]，T[2]==T[5]
Next[6]=-1根据(2)，虽然前面是abC=abC，T[3]==T[6]
下一个[7]=4根据(3)，前面有abCa=abCa，还有T[4]！=T[7]
如果T[4]==T[7]，即t="adcadcad "，那么会是这样：next[7]=0而不是=4，因为T[4]==T[7]。
如果你觉得有点被理解了，那么
练习：求t=" AAAAAAAAAB "的模式函数值，用下面的求模式函数值的函数来验证。
下一个函数值到底是什么意思？有些之前已经说过了，这里总结一下。
设模式串T在串S中找到，如果S[m]！=T[n]，那么，取T[n]的模式函数值nexT[n]，
1.next[n]=-1表示S[m]和T[0]已经间接比较过，不相等。下次比较S[m 1]和T[0]。
2.next[n]=0表示在比较过程中出现了不平等。下次比较S[m]和T[0]。
3.next[n]=k ^ 0但是k ^ n，这意味着S[m]的前k个字符和T中的前k个字符已经被间接比较为相等。下一次比较S[m]和T[k]相等吗？
4.其他值，不可能。
4.求字符串t的next[n]的模式值的函数。
说了这么多，你觉得找字符串T的next[n]的模式值复杂吗？让我写一个函数。现在，我宁愿去天空。好在有现成的功能。我钦佩发明KMP算法和编写这个函数的祖先。明白了我会反复思考。下面是这个函数：
void get_nextval(const char *T，int next[])
//找到模式字符串T的下一个函数值，存储在数组next中。
int j=0，k=-1；
next[0]=-1；
while ( T[j/* 1*/]！=/0 )
{
if (k==-1 T[j]==T[k])
{
j；k；
if (T[j]！=T[k])
next[j]=k；
其他
next[j]=next[k]；
}//如果
其他
k=下一个[k]；
}//当
////这里是我添加的显示部分。
//for(inti=0；我我)
//{
//cout next[I]；
//}
//cout endl；
}//get_nextval
另一种写法也差不多。
void getNext(const char* pattern，int next[])
next[0]=-1；
int k=-1，j=0；
while(模式[j]！=/0)
{
如果(k！=-1模式[k]！=模式[j])
k=下一个[k]；
j；k；
if(模式[k]==模式[j])
next[j]=next[k]；
其他
next[j]=k；
}
////这里是我添加的显示部分。
//for(inti=0；我我)
//{
//cout next[I]；
//}
//cout endl；
下面是KMP模式匹配程序，你可以用它来验证。记得加上上面的函数。
#包含iostream.h
#包含字符串. h
Intkmp (const char * text，const char * pattern)//const表示该参数的值在函数内部不会改变。
如果(！正文！Pattern Pattern[0]==/0 Text[0]==/0 )//
return-1；//空指针或空字符串，返回-1。
int len=0；
const char * c=Pattern
while(*c！=/0)//移动指针的速度比下标快。
{
len//字符串长度。
}
int * next=new int[len 1]；
get_nextval(Pattern，next)；//查找模式的下一个函数值
int index=0，i=0，j=0；
while(正文[i]！=/0 模式[j]！=/0 )
{
if(文本[i]==模式[j])
{
我；//继续比较后续字符
j；
}
其他
{
index=j-next[j]；
if(下一个[j]！=-1)
j=next[j]；//模式字符串向右移动
其他
{
j=0；
我；
}
}
}//当
接下来删除[]；
if(Pattern[j]==/0 )
回报指数；//匹配成功
其他
return-1；
int main()//abCabCad
char * text= bababccadcaabcaaababcbaaaaaaaacababcaabc ；
char * pattern= adCadCad
//getNext(pattern，n)；
//get_nextval(pattern，n)；
cout KMP(文本，模式)endl
返回0；
5.表达模式值的其他方法
上述字符串的模式值表示方法是最好的表示方法。我们可以从字符串的模式值中得到很多信息，下面称之为第一种表示方法。在第二个表示中，虽然也定义了next[0]=-1，但是-1永远不会出现在后面。除了next[0]之外，其他模式值next[j]=k(0k j)的意义可以简单地看作：下标j的字符的前k个字符与前k个字符相同，这里不需要t[j]！=T[k].其实next[0]也可以定义为0(后面给出的查找字符串模式值的函数和匹配字符串模式的函数是next[0]=0)。这样，next[j]=k(0k j)的含义就可以简单地看成：下标j的字符的前k个字符与前k个字符相同。第三种表示方法是第一种表示方法的变体，即，通过第一种方法获得的模式值被加1到每个值，并且获得第三种表示方法。第三种表示方法，从论坛上看到的，没看到详细解释。我猜是为了那些编程语言：数组的下标从1开始而不是0。
以下是一些方法示例：
表1。
字符串模式值的第一种表示和第二种表示见表1:
第一种表示方法，next[2]=-1，意思是T[2]=T[0]，T[2-1]！=T[0]
第二种表示，next[2]=0，表示T[2-1]！=T[0]，但是T[0]和T[2]不相等也没关系。
第一种表示，next[3]=0，意味着尽管T[2]=T[0]，T[1]==T[3]
第二个表达式，next[3]=1，表示T[2]=T[0]，他不关心T[1]和t[3]是否相等。
第一种表示方法，next[5]=-1，表示T[5]=T[0]，T[4]！=T[0]，T[3]T[4]！=T[0]T[1]，T[2]T[3]T[4]！=T[0]T[1]T[2]
第二个表示，next[5]=0，表示T[4]！=T[0]，T[3]T[4]！=T[0]T[1]，T[2]T[3]T[4]！=T[0]T[1]T[2]，但T[0]和T[5]不相等也没关系。换句话说：即使t [5]= x ，或者t [5]= y ，t [5]= 9 ，还有next[5]=0。
从这里我们可以看出，字符串的模式值的第一种表示法可以表示更多的信息，而第二种表示法更简单，不容易出错。当然，第一种表示方法写的模式匹配函数效率更高。比如在字符串S=" adccadcadcadcad9876543 "中匹配字符串T=" adccadcadcadcad9876543 "，那么第一种表示方法写的模式匹配函数就会和S[6]进行比较！当=T[6]时，取next[6]=-1(表3)，可以表示这样大量的信息：s[3]s[4]s[5]==T[3]T[4]T[5]==T[0]T[1]T[2]。=T[6]，T[6]==T[3]==T[0]，所以S[6]！=T[0]，然后比较S[7]和T[0]。如果把第二种表示方法写的模式匹配函数比作S[6]！当=T[6]时，取next[6]=3(表3)，只能表示：s[3]s[4]s[5]=T[3]T[4]T[5]==T[0]T[1]T[2]，而不能。如果不相等，则取next[3]=0，即s [3] s [4] s [5]=T[0] t [1] t [2]，但不会确定t[3]和T[0]不相等，即S[6]和T[0]不相等。是不是比第一个表示写的模式匹配函数多了几个转折？
为什么解释完第一种表象，还要讲不如第一种表象的第二种表象呢？原因是：一开始看了一个严为民的讲座，她给出的模式值的表示方法是我这里的第二种表示方法，如图：
她说：“下一个函数值的意义是：当S[i]出现的时候！=T[j]，接下来的比较应该在S[i]和T[next[j]]之间进行。”很简洁，但是不清楚。反反复复也没明白为什么。而她给出的算法得到的模式值就是下一个值，我这里说的第一个表示方法，就是前面的get_nextval()函数。匹配算法也有缺陷。所以我在这里发帖说她错了：
http://community..net/Expert/topic/4413/4413398.xml?温度=.2027246
现在看来，她没有错，但是有戴皇冠的嫌疑。不知道有没有人第一次学这个，不用参考其他资料和明白人的解释就能理解这个算法(我指的不仅仅是算法的大致思路，而是为什么定义和例子中的next[j]=k(0k j)，算法中的next[j]=k(-1k j)。我的良心说：光是看这个讲座，我就很佩服这个老师。不仅讲课讲得好，而且声音悦耳，讲课结构严谨，恰到好处。在KMP有一个小错误。可能是编一本书的时候，抄了这本书的例子，那本书的算法，结果跟数字不太吻合。因为找不到原著了，而且据一些网友说，已经不是这样了，可能吧。说起来，教授研究的问题比这个深刻很多倍，根本没时间去推导这个小算法。总之，瑕不掩瑜。
让我们言归正传。下面是我写的函数，用来寻找第二个表示所代表的模式值。为了从S的任意位置匹配T，“当S[i]出现！=T[j]，接下来的比较应该在S[i]和T[next[j]]之间进行。”定义next[0]=0。
void myget_nextval(const char *T，int next[])
//找到模式字符串T的下一个函数值(第二个表示)，存储在数组next中。
int j=1，k=0；
next[0]=0；
while ( T[j]！=/0 )
{
if(T[j]==T[k])
{
next[j]=k；
j；k；
}
else if(T[j]！=T[0])
{
next[j]=k；
j；
k=0；
}
其他
{
next[j]=k；
j；
k=1；
}
}//当
for(inti=0；我我)
{
cout next[I]；
}
cout endl
}//myget_nextval
下面是模式值的第二种表示的匹配函数(next[0]=0)。
int my_KMP(char *S，char *T，int pos)
int i=pos，j=0；//pos(s的下标0pos strlength(s))
while ( S[i]！=/0 T[j]！=/0 )
if (S[i]==T[j])
{
我；
j；//继续比较后续字符
}
else //ababcaabc
//000120112
{ //-10-102 -1102
我；
j=next[j]；/*当S[i]出现的时候！=T[j]，
接下来的比较应该在S[i]和T[next[j]]之间进行。需要Next[0]=0。
使用全局数组next[]在这两个简单的演示函数之间传递值。*/
}
}//当
if ( T[j]==/0 )
返回(I-j)；//匹配成功
其他
return-1；
} //我的KMP
不及物动词后记- KMP的历史
[这段话被抄了]
库克在1970年证明的一个理论表明，任何可以用一种叫做下推自动机的计算机抽象模型解决的问题，也可以用一台实际的计算机(更准确地说，用随机存取机)在与问题规模相对应的时间内解决。特别地，这个理论暗示了有一个算法可以在大约m ^ n内解决模式匹配问题，其中m和n分别是存储文本和模式字符串数组的最大索引。Knuth和Pratt努力重建Cook的证明，从而创造了这个模式匹配算法。几乎在同一时间，莫里斯在考虑设计文本编辑器的实际问题时，创建了几乎相同的算法。这里可以看出，并不是所有的算法都是在“灵光一现”中被发现的，理论计算机科学在某些情况下确实会被运用到实际应用中。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。