如何证明Manacher算法的时间复杂度是O(n)?

就是求最长回文子串的那个算法
关注者
66
被浏览
5318

5 个回答

谢邀:
我希望:题主事先已经知道了Manacher这个算法,以及该算法的细节,以及能看得懂这个链接里面的介绍hdu3068之manacher算法+详解如果不能做到以上几点,那么我没什么好讲的

然后我结合链接里面的内容讲一下时间复杂度。
如果我们能证明maxlen或i+k的每增加1只需要有限个单位的时间,而当maxlen增加到2n+1时这个算法也就结束了,或者当i+k=2N+1时这个算法也就结束了。

大概如上图所示,那个黑线的右边已经到顶了。。。右边红线的长度一定会大于右边蓝线的长度,也就是没有必要迭代了,不可能找到更长得回文串了。。或者i+k到了n该算法自然结束。。。T(N)<2(N+1)+ 2(N+1) = O(N) 即可得证

现在
我们现在证明maxlen或i+k的每增加1只需要有限个单位的时间
如下图

如果是1这种情况,明显我们每次执行while就能够让maxlen+1,执行完i+k会+1
如果是2,那么分成三种情况
第一种.单位时间,让i+k向右移动一下,(那个橙色不可能超过黑色线右端,一旦超过,黑色线就得重画,而橙色线本身可以到达黑色线右端,所以直接就是结果,也就是即使写了while也必定会在第一次循环)

第二种.单位时间让i+k向右移动一下,(如果右边的蓝色线能扩展,那么对称过来的左边的蓝色线也能扩展了,而左边的我们已经计算出来没法扩展了,所有,右边的蓝色线就是界限,即使写了while也必定在第一次循环退出)

第三种情况,每次执行以下while,那么就会让maxlen向右移动一下。。。while结束后i+k移动一下

所以综合以上有所情况,每个单位运算要么让maxlen向右移动一下,要么让i+k向右移动一下。而i+k<2N+1,且maxlen<2N+1,所以,整个算法的运行时间一定小于2N+1 + 2N+1 = O(N)


当然这个证明可以用势能法单纯以maxlen为标准做势能法。过程我就不讲了。其实和上面分析类似。
  • 核心代码
void manacher(char* s)
{
    int c = 0, r = 0;
    p[0] = 0;
    for( int i = 1; s[i]!='\0' ; ++i ) {
        if( r > i ) p[i] = min( p[ 2 * c - i ], r - i );
        else p[i] = 0;
        while( s[i + 1 + p[i]] == s[i - 1 - p[i]] ) p[i]++;
        if( i + p[i] > r ) {
            r = i + p[i];
            c = i;
        }
    }
}


  • 算法复杂度

从代码可以看出。
manacher算法只需要线性扫描一遍预处理后的字符串。
p[]数组的处理 i' i关于c的对称点



1. 在i < r的情况下,p的值可以在O(1)时间内确定
2. 在i>r
的情况下,p的值需要O(n)的时间内确定,但是在情况2下,每次扫描都从r+1开始,r自身的变化情况是单调递增的,这样可以保证,字符串中的每个字符最多被访问2次,所以,该算法的时间复杂度是线性O(n)

  • 只需要弄清楚两点
  1. while()循环本身的时间复杂度在没有前提条件的情况下确实是O(n)
  2. 但是这里的r(也就是上面答案中的maxlen),是不断往后走而不可能往前退的,它自身的值的变化是递增的。那么你可以明白,要进入while循环,i的值必然是比r大的,也就是说整个程序结束为止,while循环执行的操作数为n次(线性次),而字符串中的每个字符,最多能被访问到2次。时间复杂度必然为O(n)