串的模式匹配,KMP算法

串的模式匹配

现考虑一个常用操作,在字符串s(我们称为主串)中的第pos开始处往后查找,看在主串s中有没有和子串p相匹配的的,如果有,则返回字串p第一次出现的位置。

暴力求解

int Index(char s[], char p[], int pos)
{
int i=pos,j=0;
while(s[i] != '\0' && p[j] != '\0') /* 没有到达结尾 */
if(s[i] == p[j]) {
i++; j++; /* 如果相等继续比较后面的字符 */
}
else {
i = i-j+1; /* i回到比较起点的后一个 */
j = 0; /* j从新开始 */
} if(p[j] == '\0') /* 匹配成功 */
return i-j; /* 返回成功那次的比较起点 */
else
return -1; /* 返回 -1 代表找不到位置 */
}

KMP算法

相比暴力算法多了一个字串的next映射函数,而该算法的核心和技巧就在于next数组上的求解。

int KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen)
{
//①如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}

next的求解

void GetNext(char* p,int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1) {
//p[k]表示前缀,p[j]表示后缀
if (k == -1 || p[j] == p[k]) {
++k;
++j;
next[j] = k;
}
else {
k = next[k];
}
}
}

或者

//优化过后的next 数组求法
void GetNextval(char* p, int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前缀,p[j]表示后缀
if (k == -1 || p[j] == p[k]) {
++j;
++k;
//较之前next数组求法,改动在下面4行
if (p[j] != p[k])
next[j] = k; //之前只有这一行
else
//因为不能出现p[j] = p[ next[j ]],所以当出现时需要继续递归,k = next[k] = next[next[k]]
next[j] = next[k];
}
else {
k = next[k];
}
}
}
上一篇:【转】探索 ConcurrentHashMap 高并发性的实现机制


下一篇:《数据结构》之串的模式匹配算法——KMP算法