您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

Manacher算法 || 回文的高效算法

卞振伟2018-11-26【ACM||算法】人已围观

简介Manacher算法详解与应用
时间复杂度O(n)
概念
<1>回文半径数组
<2>最右回文半径

   算法伪代码描述:
             <1>i在R外  暴力
             <2>i在R内 
                 (1)i回文在L,R内                      O(1)
                 (2)i回文在L,R外                      O(1)
                 (3)i回文左边界与L压线,从R右边界扩

                    
                   
      建议读者使用以下测试数据,按照上面的伪代码算法描述推理一至两遍
                   (1) t[f(aBa)kTk(aBa)f]s
                   (2) (ab[cEcba)tTtab(cEc)]f
                   (3) [(abcEcba)fFf(abcEcba)]s

                   []对应L,R     ()对应i的回文

#include<bits/stdc++.h>
 
using namespace std;
 
char *manacherString(string s){
    char *res = new char[s.length() * 2 + 1];
    int index = 0;
    for (int i = 0; i < s.length() * 2 + 1;i++)
        res[i] = (i & 1) ? s[index++] : '#';
    return res;
}
 
int manacher(string s){
    if (s.length() == 0)
        return 0;
    char *charArr = manacherString(s);
    int charArrLen = s.length() * 2 + 1;
    int *pArr = new int[charArrLen];
    int C = -1, R = -1;    //C为中心  R右为边界
    int Max = INT_MIN;
    for (int i = 0; i < charArrLen ; i++){
        pArr[i] = R > i ? min(pArr[2 * C - i] , R-i) : 1;       //2、3种情况  1、4(边界)种情况
        while (i + pArr[i] < charArrLen && i - pArr[i] > -1){   //判定是否越界
             if (charArr[i + pArr[i]] == charArr[i - pArr[i]])  //暴力扩
                pArr[i]++;
             else
                break;
        }
        if (i + pArr[i] > R){    //更新右边界
            R = i + pArr[i];
            C = i;
        }
        Max = max(Max , pArr[i]);
    }
    return Max - 1;//因增加#原因
}
 
int main(){
    string s;
    cin>>s;
    cout<<manacher(s)<<endl;
}

--------------------- 
作者:以梦为马诗酒趁年华 
来源:CSDN 
原文:https://blog.csdn.net/weixin_41679721/article/details/82258186 
版权声明:本文为博主原创文章,转载请附上博文链接!

Tags:ACM   编程   算法

很赞哦! ()

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00