1、字符串转换
例如：
S=”abba”，变为T=”#a#b#b#a#” ；
S=”abcba”，变化为T=”#a#b#c#b#a#”。
改造的目的是将字符串的长度变为奇数，这样就可以统一的处理奇偶的情况了。
2、计算新字符串的回文半径
- 创建数组P,P[i]表示以T[i]为中心的回文半径。举个例子：
<br />根据回文的特性，i点关于Mi的对称点j的值p[j]，而且，P[i] = P[j]。<br /><br />根据对称关系，i-Mi = Mi - j得到j = 2Mi - i。<br />当 i < R时<br />如果，P[i] < R - i，说明以元素i为中心的回文长度一定在区间(R,L)内。<br />如果，P[i] >= R - i,说明以第i个字符为中心的回文半径可能已经超出R了，至于是否超出，要看第(R+1)个字符关于点i是否对称。<br />当 i >= R时，只能做以i为中心的字符对称匹配，即从p[i]=1开始。<br />代码如下：<br />#include<bits/stdc++.h><br />using namespace std;<br />const int N =4e5+5;<br />char s[N];<br />char str[N<<1];<br />int p[N<<1];<br />int init() //将字符串进行转化<br />{<br /> int len=strlen(s);<br /> str[0]='@';<br /> str[1]='#';<br /> int j=2;<br /> for (int i=0;i<len;i++)<br /> str[j++]=s[i],str[j++]='#';<br /> str[j]=0;<br /> return j; //返回得到的新字符串的长度<br />}<br />int manacher()<br />{<br /> int len=init();<br /> int mx=0;<br /> int id=0;<br /> int ans=0;<br /> for (int i=1;i<len;i++)<br /> {<br /> if(i<mx)<br /> p[i]=min(p[2*id-i],mx-i); //在 i 处小于最大边界的话，则初始<br /> else // 半径为与之对称点的半径p[2*id-i]与mx-id的最小值。<br /> p[i]=1; //在 i 处大于边界的话，则初始半径就是1<br /> while(str[i-p[i]]==str[i+p[i]])p[i]++; //循环找到最大的半径<br /> if(p[i]+i>mx) //如果 i 处的边界大于了最大边界，就更新最<br /> { //大边界mx的值，还有中心id的值。<br /> mx=p[i]+i;<br /> id=i;<br /> }<br /> ans=max(ans,p[i]-1); //取出最大的回文长度<br /> }<br /> return ans;<br />}
若有收获，就点个赞吧
0 人点赞
