KMP - 字符串查找算法

Knuth-Morris-Pratt 字符串查找算法

/* KMP字符串查找算法 */
/* 返回文本串Text[]首次与模式串Patten[]匹配的子串的首字符的秩 */
/* 核心思想是：某个字符Patten[j]!=Text[i]时，滑动Patten[]，使得Patten[next[j]]对齐Text[i]，继续比对； */
/* 查询表Next[]的使用，避免了比对失配时无谓地回退到Patten[0]重新开始比对； */
int KMPMatch(char* Patten, char* Text)
{
int* buildNext(char*);

int *Next = buildNext(Patten);
int n = strlen(Text);
int m = strlen(Patten);
int i = 0, j = 0;

while (j < m && i < n)
{
if (j < 0 || Patten[j] == Text[i])
{
i++;
j++;
}
else
{
j = Next[j];
}
}

delete [] Next;

return i - j;
}

/* 建立查询表Next[] */
/* 根据Patten[]的特性建立Next[] */
/* 在模式串与文本串比对时，当Text[i] != Patten[j]，则移动Patten[]使得Patten[Next[j]]对齐Text[i]比对； */
int* buildNext(char* Patten)
{
int m = strlen(Patten), j = 0;
int *Next = new int [m];

/* Next[0] = -1 作为通配符哨兵，即当j = Next[j] = -1时，对齐Patten[-1 + 1]与Text[i + 1]比对 */
int t = Next[0] = -1;
while (j < m - 1)
{/* 注意循环条件 */
if (t < 0 || Patten[t] == Patten[j])
{
j++;
t++;
/* 由于Patten[0 .. t - 1] == Patten[j - t .. j - 1]且Patten[t] == Patten[j]， */
/* 若令Next[j] = t，即移动Patten[]使得Patten[t]对齐Text[i]比对，亦有Text[i] != Patten[t]，这是一次多余的比对。 */
/* 所以，应移动Patten[]使得Patten[Next[t]]对齐Text[i]比对，即令Next[j] = Next[t]。 */
Next[j] = (Patten[j] == Patten[t] ? Next[t] : t);
}
else
{
t = Next[t];
}
}

return Next;
}