字符串模式匹配——KMP算法（时间复杂度为
O（m+n））
KMP字符串模式匹配通俗点说就是⼀种在⼀个字符串中定位另⼀个串的⾼效算法。简单匹配算法的时间复杂度为O(m*n)，KMP匹配算法，可以证明它的时间复杂度为O(m+n).。
⼀.简单匹配算法
先来看⼀个简单匹配算法的函数：
int Index_BF ( char S[ ], char T[ ], int pos )
{
int i = pos, j = 0;
while ( S[i+j] != '\0'&& T[j] != '\0')
if ( S[i+j] == T[j] )
j ++; // 继续⽐较后⼀字符
el
{
i ++; j = 0; // 重新开始新的⼀轮匹配
}
if ( T[j] == '\0')
return i; // 匹配成功返回下标
el
return -1; // 串S中(第pos个字符起)不存在和串T相同的⼦串
}
此算法的思想是直截了当的：将主串S中某个位置i起始的⼦串和模式串T相⽐较。即从 j=0 起⽐较 S[i+j] 与 T[j]，若相等，则在主串 S 中存在以 i 为起始位置匹配成功的可能性，继续往后⽐较( j逐步增1 )，直⾄与T串中最后⼀个字符相等为⽌，否则改从S串的下⼀个字符起重新开始进⾏下⼀轮的"匹配"，
即将串T向后滑动⼀位，即 i 增1，⽽ j 退回⾄0，重新开始新⼀轮的匹配。
⼜⼀次发⽣了失配，所以T下标⼜回溯到开始，S下标增1，然后再次⽐较。这次T中的所有字符都和S中相应的字符匹配了。函数返
天涯情感社区
回T在S中的起始下标3。如图：
⼆. KMP匹配算法
红岩感悟
KMP匹配算法和简单匹配算法效率⽐较，⼀个极端的例⼦是：
在S=“AAAAAA…AAB“(100个A)中查找T=”AAAAAAAAAB”, 简单匹配算法每次都是⽐较到T的结尾，发现字符不同，然后T的下标回溯
也就是说，如果开始的两个字符之后的第三个字符也为’d’，那么，尽管T[5]==’d’的前⾯有2个字符和开始的两个字符相同，T[5]==’d’的模式函数值也不为2，⽽是为0。
有⼈可能会问：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=“abaabd”呢？答：这种情况，当⽐较到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=”abaabcabdabba”在S中搜索T=“abaabd”呢？答：这种情况当⽐较到S[5]和T[5]时，发现不等，就去看next[5]的
值，next[5]=2，意思是前⾯的⽐较过了，其中，S[5]的前⾯有两个字符和T的开始两个相等，接下来去⽐较S[5]和T[2]吧。
总之，有了串的next值，⼀切搞定。那么，怎么求串的模式函数值next[n]呢？（本⽂中next值、模式函数值、模式值是⼀个意思。）三. 怎么求串的模式值next[n]
定义：
（1）next[0]= -1 意义：任何串的第⼀个字符的模式值规定为-1。蒲公英幼儿园
（2）next[j]= -1 意义：模式串T中下标为j的字符，如果与⾸字符相同，且j的前⾯的1—k个字符与开头的1—k个字符不等（或者相等
但T[k]==T[j]）（1≤k<j）。如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]
（3）next[j]=k 意义：模式串T中下标为j的字符，如果j的前⾯k个字符与开头的k个字符相等，且T[j] != T[k]（1≤k<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].（1≤k<j）;
(4) next[j]=0 意义：除（1）（2）（3）的其他情况。
举例：
01）求T=“abcac”的模式函数的值。
next[0]= -1 根据（1）
next[1]=0 根据 (4) 因（3）有1<=k<j；不能说，j=1,T[j-1]==T[0]
next[2]=0 根据 (4) 因（3）有1<=k<j;（T[0]=a）!=（T[1]=b）
next[3]= -1 根据 (2)
next[4]=1 根据 (3) T[0]=T[3] 且 T[1]=T[4]
即
下标01234
T a b c a c
next-100-11
若T=“abcab”将是这样：
下标01234
T a b c a b
next-100-10居间行为
为什么T[0]==T[3]，还会有next[4]=0呢, 因为T[1]==T[4], 根据 (3)” 且T[j] != T[k]”被划⼊（4）。
02）来个复杂点的，求T=”ababcaabc” 的模式函数的值。
next[0]= -1 根据（1）
next[1]=0 根据(4)
360截图
next[2]=-1 根据 (2)
next[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]
next[5]=-1 根据 (2)
next[6]=1 根据 (3) T[0]=T[5] 且T[1]!=T[6]
next[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]
即
下标012345678
T a b a b c a a b c
next-10-102-1102
吴伯箫简介
只要理解了next[3]=0，⽽不是=1，next[6]=1，⽽不是= -1，next[8]=2，⽽不是= 0，其他的好象都容易理解。
03)来个特殊的，求 T=”abCabCad” 的模式函数的值。
下标01234567
T a b C a b C a d
next-100-100-14
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]
next[7]=4 根据 (3) 前⾯有abCa=abCa，且 T[4]!=T[7]
若T[4]==T[7]，即T=” adCadCad”，那么将是这样：next[7]=0, ⽽不是= 4，因为T[4]==T[7].
下标01234567
T a d C a d C a d
next-100-100-10
如果你觉得有点懂了，那么
练习：求T=”AAAAAAAAAAB” 的模式函数值，并⽤后⾯的求模式函数值函数验证。
意义：
next 函数值究竟是什么含义，前⾯说过⼀些，这⾥总结。
设在字符串S中查找模式串T，若S[m]!=T[n]，那么，取T[n]的模式函数值next[n],
<[n]= -1 表⽰S[m]和T[0]间接⽐较过了，不相等，下⼀次⽐较 S[m+1] 和T[0]
<[n]=0 表⽰⽐较过程中产⽣了不相等，下⼀次⽐较 S[m] 和T[0]。
<[n]= k >0 但k<n, 表⽰,S[m]的前k个字符与T中的开始k个字符已经间接⽐较相等了，下⼀次⽐较S[m]和T[k]相等吗？
4.其他值，不可能。
四. 求串T的模式值next[n]的函数
void get_nextval(const char *T, int next[])
{
// 求模式串T的next函数值并存⼊数组 next。
int j = 0, k = -1;
next[0] = -1;
while ( T[j] != '/0' )
{
if (k == -1 || T[j] == T[k])
{
++j; ++k;
if (T[j]!=T[k])
next[j] = k;
el
next[j] = next[k];
}// if
el
k = next[k];
}// while
}
下⾯是KMP模式匹配程序
int KMP(const char *Text,const char* Pattern) //const 表⽰函数内部不会改变这个参数的值。
{
if( !Text||!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);//求Pattern的next函数值 int index=0,i=0,j=0;
while(Text[i]!='\0' && Pattern[j]!='\0' )
{
if(Text[i]== Pattern[j])
{
++i;// 继续⽐较后继字符
++j;
}
el
{
index += j-next[j];
if(next[j]!=-1)
j=next[j];// 模式串向右移动
el
{
j=0;
十二属相顺序
++i;
}
}
}//while
delete []next;
if(Pattern[j]=='\0')
return index;// 匹配成功，返回匹配⾸字符下标
el
el
return -1;
}
测试程序：
int main()
{
脱式计算五年级char* text="abcdefgh123456789465asdac789asd4654qw5e46a1"; char*pattern="4654qw";
int pos = KMP(text,pattern);
if(pos==-1)
printf("⽆法找到匹配字符串！\n");
el
printf("匹配成功！匹配⾸字符下标:%d\n",pos);
system("pau");
return 0;
}
