KMP算法也算接触很久了,今天却突然发现不知道那个的复杂度是怎么来的
于是想啊想,查啊查,总结如下
设代码为

s=0;  
for(i=1;i<=m,i++){  
    while(s>0&&a[i]!=b[s+1])s=next(s)  
    if(a[i]==b[s+1])s++;  
    if(s==n) return (i-n)
}

分析的关键是那个while循环循环会让s减少
而s又只会在第五行增加,于是j最多增加m次,
在然后我们就知道j最多减少m次(因为不能为负)
平摊到每个for上就是一次
所以复杂度就是O(m)了
不过也有书上说是O(m+n)
这个就不是很明白了... 想想在说...