Manacher算法：寻找最长回文子串长度的高效算法

(本文最后判断区间回文有改动&＃xff0c;emm之前写错了&＃xff0c;你这么聪明一定看出来了)

该算法用于寻找当前串中最长的回文子串长度。

为了避免误人子弟&＃xff0c;也可以直接去看思路清晰&＃xff0c;简单易懂的博客&＃xff1a;https://blog.csdn.net/dyx404514/article/details/42061017

这个大神写的各种算法的模板和讲解都很棒哦。

①暴力找&＃xff1a;

我们选取一个点O&＃xff0c;然后要考虑这个点作为回文串中心可能形成最长回文串的三种情况&＃xff1a;

回文长度为奇数的情况

xxOxx

回文长度为偶数的情况&＃xff1a;

xxxOxx

xxOxxx

O&＃xff08;N²&＃xff09;的复杂度妥妥的。

②Manacher&＃xff1a;

首先该算法是O&＃xff08;N&＃xff09;的。

然后解决了上述需要分三种情况讨论的问题。

假设一个待匹配的串为aabaa

我们会把他变成

&＃xffe5;#a#a#b#a#a#$

也就是用&＃xff08;字符串长度&＃43;1个&＃xff09;#把字符一个个分开&＃xff0c;旁边再加两个不同的字符防止匹配的时候越界。

为什么这样处理就可以不用分情况了呢&＃xff1f;

这个问题我们在构造好了我们的Len数组&＃xff0c;了解这个数组的含义了之后再说。

我们对这个船新的串使用manacher算法

③Len数组含义与构造&＃xff1a;

Len[i]表示以i为中心的回文串往右边延伸了多少

eg&＃xff1a;&＃xffe5;#a#a#b#a#a#$&＃xff0c;Len【6】 &＃61;  6&＃xff0c;Len【2】&＃61; 2 &＃xff0c;Len【1】 &＃61; 1

构造核心思想与kmp&＃xff0c;exkmp差不多&＃xff0c;就是根据已经匹配的&＃xff0c;让当前能够最大限度的偷懒&＃xff08;得到当前已知匹配的部分&＃xff09;

PO表示当前Len能够向右延伸最远的回文串中点坐标。

mx就是延伸最右位置的坐标。

这两个都是辅助用于判断当前i位置有几位已经确定回文可以不用比了。

具体匹配过程的图示&＃xff1a;&＃xff08;红色块最右即为mx&＃xff09;

板子&＃xff1a;&＃xff08;主函数 字符串从0开始输入&＃xff09;

const int maxn&＃61;1000010;
char str[maxn];//原字符串
char tmp[maxn<<1];//转换后的字符串
int Len[maxn<<1];
//转换原始串
int INIT(char *st)
{int i,len&＃61;strlen(st);tmp[0]&＃61;&＃39;&＃64;&＃39;;///开头加一个不等于#也不等于字符串的字符&＃xff0c;这样就不用判断左边越界了&＃xff0c;那么右边万一比到n&＃43;1怎么办呢&＃xff1f;有\0吗&＃xff1f;不&＃xff0c;\0在n处&＃xff0c;解决办法看16行for(i&＃61;1;i<&＃61;2*len;i&＃43;&＃61;2){tmp[i]&＃61;&＃39;#&＃39;;tmp[i&＃43;1]&＃61;st[i/2];}tmp[2*len&＃43;1]&＃61;&＃39;#&＃39;;tmp[2*len&＃43;2]&＃61;&＃39;$&＃39;;///结尾搞一个不是&＃64;也不是#的字符tmp[2*len&＃43;3]&＃61;0;return 2*len&＃43;1;//返回转换字符串的长度
}
//Manacher算法计算过程
int MANACHER(char *st,int len)
{int mx&＃61;0,ans&＃61;0,po&＃61;0;//mx即为当前计算回文串最右边字符的最大值for(int i&＃61;1;i<&＃61;len;i&＃43;&＃43;){if(mx>i)Len[i]&＃61;min(mx-i,Len[2*po-i]);//在Len[j]和mx-i中取个小elseLen[i]&＃61;1;//如果i>&＃61;mx&＃xff0c;要从头开始匹配while(st[i-Len[i]]&＃61;&＃61;st[i&＃43;Len[i]])Len[i]&＃43;&＃43;;if(Len[i]&＃43;i>mx)//若新计算的回文串右端点位置大于mx&＃xff0c;要更新po和mx的值{mx&＃61;Len[i]&＃43;i;po&＃61;i;}ans&＃61;max(ans,Len[i]);}return ans-1;//返回Len[i]中的最大值-1即为原串的最长回文子串额长度
}


实在理解不了去看看exkmp&＃xff0c;真的感觉是一毛一样的&＃xff1a;https://blog.csdn.net/weixin_43768644/article/details/94644776

④&＃xff1a;Len数组的使用

注意Len数组使用是都是看原字符串第几个字符&＃xff08;1~n&＃xff09;&＃xff0c;不是看下标&＃xff08;0~i-1&＃xff09;&＃xff0c;这个比较重要

&＃xff08;0&＃xff09;基本的认识

         Len[i]对应两种情况&＃xff1a;

         ①当前是‘#’时&＃xff0c;Len[i] 必定为奇数&＃xff0c;eg&＃xff1a;a#a  #  a#b&＃xff0c;Len[中间&＃39;#&＃39;的下标] &＃61; 3

         那么这个Len[i]就对应原字符串中偶数长度的回文串&＃xff0c;你可以求原串的回文中点&＃xff08;i/2表示靠左的中点&＃xff09;&＃xff0c;然后最大回文半径

         等于Len[i]/2     &＃xff08;因为奇数会向下取整&＃xff09;

         ②当前是字母&＃xff0c;Len[i]比为偶数&＃xff0c;eg&＃xff1a;a#a# b #a#b 对应奇数长度回文串&＃xff0c;i/2表回文中点&＃xff0c;Len[中间&＃39;b&＃39;的下标] &＃61; 4

         i/2是回文中心&＃xff0c;Len[i]/2是回文半径&＃xff08;&＃61;2&＃xff0c;对于aba&＃xff09;

         下面这三个应该没什么用。

         i表示第i个字符

         判断当前点作为奇数长度回文中点的最长回文长度  --->Len[i*2]-1

         判断当前点作为偶数长度回文左中点的最长回文长度  --->Len[i*2&＃43;1]-1

         判断当前点作为偶数长度回文左中点的最长回文长度  --->Len[i*2-1]-1

&＃xff08;1&＃xff09;判断原字符串中[l,r]是否回文&＃xff08;l&＃xff0c;r表示第几个字母&＃xff09;

         Len[l&＃43;r]-1>&＃61;r-l&＃43;1    &＃xff1f;  是回文&＃xff1a;不是回文

         证明方法&＃xff1a;根据给出区间长度奇偶分类&＃xff0c;运用&＃xff08;0&＃xff09;里面的基本知识判断就可以

&＃xff08;2&＃xff09;求出整个串的回文串总数

         根据&＃xff08;0&＃xff09;所说的&＃xff0c;遍历加了‘#’的那个串分析每个点做中点的最长回文半径即可

&＃xff08;3&＃xff09;求出本质不同的回文串的数量

         分析&＃xff1a;首先每一个点开始匹配前会先尽可能得到已知匹配部分来减少当前匹配&＃xff0c;然后这部分我们不用判断是否出现过&＃xff0c;因为肯定出现过。然后剩余要匹配部分&＃xff0c;每次都对新产生这个回文串判断是否出现过&＃xff0c;&＃xff08;可能出现也可能没出现过&＃xff09;&＃xff0c;马拉车&＃43;哈希表去重即可实现。&＃xff08;模板题&＃xff1a;hihocoder1602&＃xff09;

做这些事情的复杂度和耗费的空间都比回文自动机小&＃xff08;大概&＃xff09;&＃xff0c;然后处理回文问题两者要灵活结合使用。