当前位置: 首页 > >

九:字符串的查找(P在S中的位置)kmp

发布时间:

1:蛮力匹配方法
int ViolentMatch(char *S, char *P)
{
int sLen = strlen(S);
int pLen = strlen(P);
int i = 0;
int j = 0;
while (i < sLen && j < pLen)
{
if (S[i] == P[j])
{
// 当前字符匹配成功
i++;
j++;
}
else
{
i = i - j + 1;
j = 0;
}
}
// 匹配成功,返回模式串P在文本串S中的位置,否则返回-1
if (j == pLen)
{
return i - j;
}
else
{
return -1;
}
}

2:KMP算法
// next值会给出下一步匹配中模式串应该调到那个位置
// 而不是每次都重置i
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)
{
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j == pLen)
{
return i - j;
}
else
{
return -1;
}
}

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];
}
}
}

?



友情链接: 传奇百科网 招聘百科网 非凡百科网 游艇百科网 口红百科网 创业百科网 软木百科网