???? 字符串模式匹配我们相信大家都有遇过，然而我们也习惯用简单匹配法（即Brute-Force算法)，其基本思路就是一个个逐一对比下去，这也是我们大家熟知的方法，然而这种算法的效率并不高，但利于理解。
?
????假设主串s="ababcabcacbab",模式串为t="abcac"，我们用肉眼很容易看出匹配位置为是s[5]--s[10];利用简单匹配算法代码如下：
class="cpp">int BF(string s,string t)//Brute-Force,简单匹配算法
{
int origin=-1;//模式匹配的起始位置
for(int i=0;i<s.size();i++)
{
int k;
for(k=0;k<t.size();k++)
{
if(s[i+k]!=t[k])
break;
}
if(k==t.size())//匹配成功
{
origin=i;
break;
}
}
return origin;//返回匹配成功的位置，若为-1，则匹配失败
}
?然后这种算法效率显而易见效率并不高，其中包含了过多的不必要操作，并不能很好地达到实际工作中需要的效率。这种算法在最好的情况下时间复杂度为O(m),在最坏的情况下时间复杂度为M(nm)。
?
KMP算法
???KMP算法较Brute-Force算法有较大的改进，主要消除了主串指针的回溯，从而是算法的效率有了某种程度的提高。
?
????为了消除主串的指针回溯，需要分析模式串t，我们利用next[]数组来记录存放这些“部分匹配信息”。
next[]计算规则如下：
1）next[j]=-1;? j=0;
2)? next[j]=max(k);??? 0<k<j,p[0....k-1]=p[j-k...j-1];
3)? next[j]=0;???其他条件
?
例如：计算ababa的next[]数组值
按照上面的规则我们可以填写出下表的next[]数组
p a b a b a j 0 1 2 3 4 next[j] -1 0 0 1 2?
根据上面规则，当j=0，next[j]=-1,所以第一个a的next值为-1；
?
当j=1时，0<k<j这样的k不存在，所以属于其他条件，即为0；
?
当j=4时，0<k<j,这样的k=1,2,3,因为要求最大的K,即从大到小验证k是否满足p[0....k-1]=p[j-k...j-1]，若一个都不满足，属于其他条件，即为0，
当k=3时,str1=p[0....k-1]=aba,str2=p[j-k...j-1]=bab,str1!=str2,所以k!=3;
当k=2时,str1=p[0....k-1]=ab,str2=p[j-k...j-1]=ab,str1==str2,满足条件,所以k=2;
?
根据上面的条件，可以轻易写出next的计算函数;
//计算next数组，t为计算字符串
void calculateNext(int * & next,string t)
{
for(int j=0;j<t.size();j++)
{
bool state=true;//是否是等于0的情况
if(j==0)
*next=-1;
else
{
int k=j-1;//0<k<j,获取最大的k
while(k>0)
{
string str1="",str2="";
for(int i=0;i<=k-1;i++)
{
str1=str1+t[i];
str2=str2+t[j-k+i];
}
if(str1==str2)//若，p[0....k-1]=p[j-k...j-1];
{
*(next+j)=k;
state=false;//不是等于0的情况
break;
}
k--;
}
if(state)//满足其他条件，即为0
*(next+j)=0;
}
}
}
?
计算出匹配信息next后，我们就可以进行KMP匹配了，
主要思路是：
假设i和j分别为指示主串和模式串中正在比较的字符的当前位置，并对i 和j 赋初值0。 在匹配的过程中，若si=tj，则i和j分别增加1，继续进行比较。 否则，若j=0，si!=tj,则从s的下一个字符开始，即i增加一,若j！=0，令j=next[j]
?
理解了上面的思路，就很容易编写出KMP匹配代码：
//kmp匹配算法,s为主串，t为模式串
int KMP(int * next,string s,string t)
{
int j=0,i=0;//i为主串s正在匹配的字符，j为t正在匹配的字符
while(i<s.size()&&j<t.size())
{
if(t[j] == s[i])
{
j++;i++;
}
else
{
if(j==0)
{
i++;//若第一个字符就匹配失败，则从s的下一个字符开始
}
else
{
j = *(next+j);//,也可以j=next[j],用next确定t应回溯到的字符
}
}
}
if(j < t.size())//整个过程匹配失败
{
return -1;
}
return i-t.size();//匹配成功
//第二种写法
/*2. while(i < s.size())
{
while(j > -1 && t[j] != s[i])
j = next[j];
i++, j++;
if(j >= t.size()) return i - j;
}
return -1; */
}
?
至此，我们就完成了KMP算法的学习。在学习KMP过程中，我发了一篇“另一种”有关的KMP算法，更好理解学习，附上链接：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
?
本次KMP的源代码地址：https://github.com/longpo/algorithm
相关文章
