杭州在线制作网站,wordpress文章延迟加载,昆山装饰公司网站建设,群晖中使用wordpress1.BF算法
算法在字符比较不相等#xff0c;需要回溯#xff08;即ii-j1#xff09;#xff1a;即退到s中的下一个字符开始进行继续匹配。
最好情况下的时间复杂度为O(m)。
最坏情况下的时间复杂度为O(nm)。
平均的时间复杂度为O(nm)。
2.KMP算法
KMP算法是D.E.Knuth、…1.BF算法
算法在字符比较不相等需要回溯即ii-j1即退到s中的下一个字符开始进行继续匹配。
最好情况下的时间复杂度为O(m)。
最坏情况下的时间复杂度为O(n×m)。
平均的时间复杂度为O(n×m)。
2.KMP算法
KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的简称KMP算法。
该算法较BF算法有较大改进主要是消除了主串指针的回溯从而使算法效率有了某种程度的提高。
设串s的长度为n串t长度为m。
在KMP算法中求next数组的时间复杂度为O(m)在后面的匹配中因主串s的下标不减即不回溯比较次数可记为n所以KMP算法平均时间复杂度为O(nm)。
最坏的时间复杂度为O(n × m)。
int KMPIndex(SqString s,SqString t)
{ int next[MaxSize], i0, j0;GetNext(t,next);while (is.length jt.length) { if (j-1 || s.data[i]t.data[j]) { i;j; //i、j各增1}else jnext[j]; //i不变j后退}if (jt.length)return(i-t.length); //返回匹配模式串的首字符下标elsereturn(-1); /
由模式串t求next值的算法
void GetNext(SString t,int next[])
{ int j, k;j0; k-1; next[0]-1;while (jt.length-1){ if (k-1 || t.data[j]t.data[k]){ j; k;next[j]k;}else knext[k];}
}
