如何证明Manacher算法的时间复杂度是O(n)? - 计算机科学 - 知乎
我希望：题主事先已经知道了Manacher这个算法，以及该算法的细节，以及能看得懂这个链接里面的介绍
hdu3068之manacher算法+详解，
如果不能做到以上几点，那么我没什么好讲的。
然后
我结合链接里面的内容讲一下时间复杂度。
如果我们能证明maxlen或i+k的每增加1只需要有限个单位的时间，而当maxlen增加到2n+1时这个算法也就结束了，或者当i+k=2N+1时这个算法也就结束了。
Read full article from 如何证明Manacher算法的时间复杂度是O(n)? - 计算机科学 - 知乎
No comments:
Post a Comment