网站后台插入程序代码用什么用/推广平台网站

manacher是在O(n)的时间内计算字符串的最大回文字串的。 相比于暴力不仅快还可以避免奇回文串还是偶回文串的问题

以下数组的下标都是从0开始的。

1.首先你需要构建一 个新的字符串：举个例子：原字符串s:abb  新字符串news：￥#a#b#b#  ￥是为了防止数组越界，新数组的长度本来为2*n+1   

2.计算新串的p数组，p[i]表示以news[i]为中心最大回文字串的半径(包括news[i]自身),那么知道p[i]有什么用呢，那么看下一步。一会会介绍p数组的求法    

3.p[i]-1（i就是新串的下标）表示以原串(i-p[i])/2为起点(i-p[i])/2+p[i]-2为终点的子回文串的长度，这样就可以找到原串子回文串的起点和终点，还有长度了。这一步就体现了新串到原串的转换  这个很好理解的，i是新串的回文串的中心减去半径就是端点/2 就是原串的端点,新串半径-1不就是原串回文串的长度了吗。有同学就会问直接求原串的中心不就好了吗，但是原串可能是偶回文串

这里介绍p的求法（p都是对新串而言的）

设mx为当前已经求得的回文串的最大右端点，以后要更新的。初始化为0.   id为mx对应的回文中心   2*id-i为i的对称位置

遍历p数组：

1.i<mx如果当前i还在id回文范围内,即i<mx  ，p[i]=min(p[2*id-i],mx-i)   

2.否则就要暴力计算

注意：p[i]==1对应原串的点是没有回文字串的。        不能通过构建的新串的mid求原串的mid的，因为原串可能是偶串，没有mid

只能求起点和终点

下面看代码吧： 其实这是个题，大家可以看下：、

https://blog.csdn.net/qq_44797733/article/details/106312709

code

#include<bits/stdc++.h>using namespace std;int manacher(string s){int len=s.length();string str="";str+="$#";for(int i=0;i<len;i++){str+=s[i];str+="#";}vector<int> p(str.size(),0);//vector是不能像数组一样直接赋值的 int mx=0,id=0;for(int i=1;i<str.size();i++){//计算p数组 if(i<mx){p[i]=min(p[2*id-i],mx-i);	}else p[i]=1;while(str[i+p[i]]==str[i-p[i]]) p[i]++;if(i+p[i]>mx){mx=i+p[i];id=i;}}int ans=0;for(int i=2;i<str.length();i++){if(p[i]==1) continue;if((i-p[i])/2+p[i]-1==len){//这里注意不能通过构建的新串的mid求原串的mid的，因为原串可能是偶串，没有mid ans=(i-p[i])/2;//(i-p[i])/2为原串子回文串的起点的下标 p[i]-1为子回文串的长度, (i-p[i])/2+p[i]-2为终点的下标 break;}	}return ans;
}
int main()
{string s;int n;cin>>n;cin>>s;cout<<manacher(s)<<endl;return 0;
}