马拉车算法(最长回文串例题密码截获)

本文算法介绍 借鉴大佬博客资料整理
Manacher算法

manacher算法，我们习惯叫他 “马拉车”算法。

Manacher算法的应用范围比较狭窄，但是它的思想和拓展kmp算法有很多共通之处，所以在这里介绍一下。Manacher算法是查找一个字符串的最长回文子串的线性算法。

在介绍算法之前，首先介绍一下什么是回文串，所谓回文串，简单来说就是正着读和反着读都是一样的字符串，比如abba，noon等等，一个字符串的最长回文子串即为这个字符串的子串中，是回文串的最长的那个。

计算字符串的最长回文字串最简单的算法就是枚举该字符串的每一个子串，并且判断这个子串是否为回文串，这个算法的时间复杂度为O(n^{3)的，显然无法令人满意，稍微优化的一个算法是枚举回文串的中点，这里要分为两种情况，一种是回文串长度是奇数的情况，另一种是回文串长度是偶数的情况，枚举中点再判断是否是回文串，这样能把算法的时间复杂度降为O(n}2)，但是当n比较大的时候仍然无法令人满意，Manacher算法可以在线性时间复杂度内求出一个字符串的最长回文字串，达到了理论上的下界。

1.Manacher算法原理与实现

下面介绍Manacher算法的原理与步骤。

首先，Manacher算法提供了一种巧妙地办法，将长度为奇数的回文串和长度为偶数的回文串一起考虑，具体做法是，在原字符串的每个相邻两个字符中间插入一个分隔符，同时在首尾也要添加一个分隔符，分隔符的要求是不在原串中出现，一般情况下可以用#号。下面举一个例子：

（1）len数组简介与性质

Manacher算法用一个辅助数组Len[i]表示以字符s[i]为中心的最长回文字串的最右字符到s[i]的长度，比如以s[i]为中心的最长回文字串是s[l,r],那么Len[i]=r-i+1。

对于上面的例子，可以得出Len[i]数组为:

 void init()//初始化 翻倍区
 {
     int i;
     s[0]='*';s[1]='#';
     for(i=0;i<le;i++)
     s[i*2+2]=str[i],s[i*2+3]='#';
     le=le*2+2;
 }

Len数组有一个性质，那就是Len[i]-1就是该回文子串在原字符串S中的长度，至于证明，首先在转换得到的字符串T中，所有的回文字串的长度都为奇数，那么对于以s[i]为中心的最长回文字串，其长度就为2Len[i]-1,经过观察可知，s中所有的回文子串，其中分隔符的数量一定比其他字符的数量多1，也就是有Len[i]个分隔符，剩下Len[i]-1个字符来自原字符串，所以该回文串在原字符串中的长度就为Len[i]-1。

有了这个性质，那么原问题就转化为求所有的Len[i]。下面介绍如何在线性时间复杂度内求出所有的Len。

（2）Len数组的计算

首先从左往右依次计算Len[i]，当计算Len[i]时，Lenj已经计算完毕。设mx为之前计算中最长回文子串的右端点的最大值，并且设取得这个最大值的位置为mx，分两种情况：

第二种情况: i>mx

如果i比mx还要大，说明对于中点为i的回文串还一点都没有匹配，这个时候，就只能老老实实地一个一个匹配了，匹配完成后要更新P的位置和对应的mid(id)以及Len[i]。

第一种情况：i<=mx
那么找到i相对于mid(id)的对称位置，设为j，那么如果Len[j]<mx-i，如下图：

那么说明以j为中心的回文串一定在以mid为中心的回文串的内部，且j和i关于位置mid(id)对称，由回文串的定义可知，一个回文串反过来还是一个回文串，所以以i为中心的回文串的长度至少和以j为中心的回文串一样，即Len[i]>=Len[j]。因为Len[j]<mid(id)-i,所以说i+Len[j]<mx。由对称性可知Len[i]=Len[j]。

如果Len[j]>=mid(id)-i,由对称性，说明以i为中心的回文串可能会延伸到mx之外，而大于mx的部分我们还没有进行匹配，所以要从mx+1位置开始一个一个进行匹配，直到发生失配，从而更新mx和对应的mid(id)以及Len[i]。

`第一种情况：i<=mx
asjdlsadasd

第二种情况: i>mx

如果i比mx还要大，说明对于中点为i的回文串还一点都没有匹配，这个时候，就只能老老实实地一个一个匹配了，匹配完成后要更新P的位置和对应的mid(id)以及Len[i]。

2.时间复杂度分析

Manacher算法的时间复杂度分析和Z算法类似，因为算法只有遇到还没有匹配的位置时才进行匹配，已经匹配过的位置不再进行匹配，所以对于T字符串中的每一个位置，只进行一次匹配，所以Manacher算法的总体时间复杂度为O(n)，其中n为T字符串的长度，由于s的长度事实上是str的两倍，所以时间复杂度依然是线性的。

下面是算法的实现，注意，为了避免更新mid(id)的时候导致越界，我们在字符串s的前增加一个特殊字符，比如说‘’,所以算法中字符串是从1开始的。

---

---

![这里写图片描述](https://img-blog.csdn.net/20180427164243799?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTIzNjIy/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/列题 1
问题 1209: 密码截获
时间限制: 1Sec 内存限制: 128MB 提交: 81 解决: 32

题目描述
Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码 进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因为截获的串太长了，而且存在多种可能的情况 （abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的 有效密码串吗？

输入
测试数据有若干行字符串，包括字母，数字，符号。（字母区分大小写）

输出
与输入相对应每一行输出一个整数，代表最长有效密码串的长度。

样例输入
ABBA
12ABBA
A
ABAKK
51233214
abaaab
样例输出
4
4
1
3
6
5

#include <stdio.h>
#include<string.h>
#define min(a,b) a>b?b:a
int le,ans=0;char str[10002];char s[20002];int len[20002];
 void init()//初始化 翻倍区
 {
     int i;
     s[0]='*';s[1]='#';
     for(i=0;i<le;i++)
     s[i*2+2]=str[i],s[i*2+3]='#';
     le=le*2+2;
 }
 void malache()//马拉车算法
 {
     int mid=0,i,mx=0;//mid 代表 当前最优解对称中心 i 表示当前处理字符位置 mx 代表当前最优解的最大下标
     for(i=1;i<le;i++)                                                   //（最长回文串最右端的下标）
     {
         if(i<mx)len[i]=min(len[2*mid-i],mx-i);//当前处理字符位置在当前最优范围内 直接查询对称点与当前已知情况减少操作
         else len[i]=1;//否则从 1 开始
         while(s[i+len[i]]==s[i-len[i]])len[i]++;//找到不是对称的点 即当前位置的回文串长度
         if(len[i]+i>mx)mx=len[i]+i,mid=i;//当前比之前的大则更新 mid mx
         if(ans<len[i])ans=len[i];//更新最长回文串长度
     }
 }
int main()
{
    while(scanf("%s",&str)!=EOF)
    {  ans=0;
        memset(s,0,sizeof(s));
        memset(len,0,sizeof(len));
      le=strlen(str);
      init();//初始化 翻倍区
      malache();
      printf("%d\n",ans-1);
        memset(str,0,sizeof(str));

<span class="token punctuation">}</span>
<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
}