Manacher算法----马拉车算法

Manacher算法----马拉车算法

看到了一个十分不错的manacher教程，原作者用java写的，我这里改成了C++

融汇贯通的自己的理解

原文：老司机开车，教会女朋友什么是「马拉车算法」_吴师兄学编程 (cxyxiaowu.com)

对于算法核心的说明，原帖讲的是浅显易懂，这里就拉两张图片，方便日后巩固

#include 
#include 
using namespace std;

char T[20002],T1[10001];
//预处理
void replay()
{
    int index = 1;
    T[0] = '#';
    int len = strlen(T1);
    //cout <<"len = " <=0&&rightMaxright){
            Maxright = i + p[i];
            center = i;
        }
        if(p[i]>Maxlen){
            Maxlen = p[i];
            address->begin = (i - p[i])/2;
            address->end = address->begin + Maxlen - 1;
        }
    }
    return *address;
}
int main()
{
    cin >> T1;
    replay();
    Address address = manacher();
    for(int i=address.begin;i<=address.end;i++){
        cout << T1[i];
    }
    return 0;
}

 

 对这个图片特别说明：三个黄C必定相等，而最左边的C和紫色的e一定不相等，所以说就有了紫色的e和最右边的c一定不相等，也就是不能匹配，从而确定p[i]的值

dui