下面是生成next数组的函数：
[cpp]
void GetNext(string Pattern, vector &next)
{
int j = 0;
int k = -1;
int lenP = Pattern.length();
next.assign(8, -1);
while (j < lenP)
{
if ((k == -1) || (Pattern[j] == Pattern[k]))
{
j++; k++;
next[j] = k;
}
else
{
k = next[k];
}
}
下面是KMP算法：
[cpp]
int KMP(string Text, string Pattern, vector &next, int TdefPos = 0)
{
int posP = 0, posT = TdefPos;
int lenP = Pattern.length();
int lenT = Text.length();
while ((posP < lenP) && (posT < lenT))
{
if ((posP == -1) || Pattern[posP] == Text[posT])
{
posP++; posT++;
}
else
{
posP = next[posP];
}
}
if (posP < lenP)
{
return -1;
}
else
{
return (lenT - lenP);
}
}