Manacher（马拉车）算法

1.前置知识

回文子串   回文的子串
最长回文子串  字符串中最长的回文子串
回文半径   设以\(i\)为中心的最大回文子串的长度为\(n\),则这个字符串第\(i\)位的回文半径为\((n+1)/2\)
2.算法流程

2.1 预处理

在处理回文子串（马拉车算法适用）的问题时，一般需要求出每一位的回文半径
经常做字符串题目的同学都知道，在处理这种问题时，最大的阻碍一般就是字符串长度的奇偶性以及边界
不难想到，我们可以在字符串的首尾分别插入一个字符来解决边界问题
也不难想到，我们可以在每一个字符的首尾都添加一个字符（包括第\(1\)个和最后一个)
由此，我们可以得到一个新字符串。
这里举一个例子，
原字符串s:ababa
进行完操作1（首尾标记）的字符串 s1: @ababa@
进行完操作2（字符插入）的字符串 s2: @#a#b#a#b#a#@
根据流程不难得出代码：
[code]cin>>a;//原串int len=strlen(a);int k=0;s[0]='$';s[1]='#';k++;for(int i=0;i

感谢，下载保存了