Manacher算法

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

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

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

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

1.Manacher算法原理与实现

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

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

Manacher算法

（1）len数组简介与性质

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

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

Manacher算法

 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]为中心的最长回文字串，其长度就为2*Len[i]-1,经过观察可知，s中所有的回文子串，其中分隔符的数量一定比其他字符的数量多1，也就是有Len[i]个分隔符，剩下Len[i]-1个字符来自原字符串，所以该回文串在原字符串中的长度就为Len[i]-1。

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

（2）Len数组的计算

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

Manacher算法

第二种情况: i>mx

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

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

#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));

    }
    return 0;
}

原文：https://blog.****.net/qq_41923622/article/details/80109897

Manacher算法

相关推荐