kmp算法是复杂度为O(n+m)的字符串匹配算法;
首先kmp算法的核心是在模式串中获得next数组,这个数组表示模式串的子串的前缀和后缀相同的最长长度;
这样在匹配的过程中如果指到不匹配的位置,模式串用next数组进行跳转到符合的位置,而目标串不需要再往回匹配,为什么是最长的相同的前缀后后缀呢?
因为只有这样才能一边避免可能漏掉的位置,一边尽量不重复已经匹配的位置;
getNext的函数:
void getNext()
{
int k = -,j = ,len = strlen(str);
next[] = -;
while(j < len)
{
if(k == -||str[j] == str[k])
{
j++;
k++;
next[j] = k;//相等的话就往后继续;
}
else k = next[k];//不等的话就相当于kmp一样,把模式串的这个子串用已经求出来的next跳转;
}
}
kmp算法代码:
int kmp()
{
int posP = ,posT = ;
int lenP = strlen(strP),lenT = strlen(strT);
while(posP < lenP&&posT < lenT)
{
if(posP == -||strP[posP] == strT[posT])
{
posP++;
posT++; }
else posP = next[posP];
if(posP == lenP)return posT-lenP;//匹配成功返回匹配成功的位置;
}
return -;//匹配失败哦;
}