您的位置: 首页  >  IT文章  >  Manacher算法--O（n）回文子串算法

Manacher算法--O（n）回文子串算法

分类: IT文章 • 2022-07-21 19:22:07
转自：http://blog.****.net/ggggiqnypgjg/article/details/6645824
O（n）回文子串算法

注：转载的这篇文章，我发现下面那个源代码有点bug。。。在下一篇博客中改正了。。

 

    这里，我介绍一下O（n）回文串处理的一种方法。Manacher算法.
原文地址：

复制代码

  1. void pk()
    {
        int i;
        int mx = 0;
        int id;
        for(i=1; i<n; i++)
        {
            if( mx > i )
                p[i] = MIN( p[2*id-i], mx-i );        
            else
                p[i] = 1;
            for(; str[i+p[i]] == str[i-p[i]]; p[i]++)
                ;
            if( p[i] + i > mx )
            {
                mx = p[i] + i;
                id = i;
            }
        }
    }

   代码是不是很短啊，而且相当好写。很方便吧，还记得我上面说的这个算法避免了很多不必要的重复匹配吧。这是什么意思呢，其实这就是一句代码。

if( mx > i)
    p[i]=MIN( p[2*id-i], mx-i);

就是当前面比较的最远长度mx>i的时候，P［i］有一个最小值。这个算法的核心思想就在这里，为什么P数组满足这样一个性质呢?
   （下面的部分为图片形式）
Manacher算法--O（n）回文子串算法
    看完这个算法，你有可能会觉得这种算法在哪会用到呢？其实回文串后缀数组也可以做。只是复杂度是O（n log n）的，而且一般情况下也不会刻意去卡一个log n的算法。可正好hdu就有这么一题，你用后缀数组写怎么都得T（当然应该是我写得太烂了）。不信的话大家也可以去试试这题。
        
        http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=140283

相关推荐