KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现。KMP算法的关键是利用匹配失败后的信息,从错误中吸取经验,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
代码:(tex为被查找的字符串,pat为要查找的模式串)
scanf("%s", tex);
scanf("%s", pat);
n = strlen(tex);
m = strlen(pat);
pi[1] = 0;
int p = 0;
for (int i = 2; i <= m; ++i)
{
while (p && pat[p + 1] != pat[i])
p = pi[p];
if (pat[p + 1] == pat[i])
p ++;
pi[i] = p;
}
p = 0;
for (int i = 1; i <= n; ++i)
{
while (p && pat[p + 1] != tex[i])
p = pi[p];
if (pat[p + 1] == tex[i])
p ++;
if (p == m)
{
printf("%d\n", i - m);
p = pi[p];
}
}