问题描述

KMP算法 时间复杂度问题

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

}

}

}

为什么这个算法的时间复杂度是o(模式串长)？
如果每一个k都要等于next[k]等于k-1？

解决方案

应该是M+N
参考：http://www.cnblogs.com/goagent/archive/2013/05/16/3068442.html