发布于2018年7月27日 由itewqq[字符串] 最长回文子串 manacher算法模板题 HDU3068 学习了一下这个算法，emmm不知道什么时候就会用到的感觉。本身功能是在O(n)时间内算出一个串的最长回文子串，其实这个过程也把每个点作为中心的最长回文串计算了一遍 这个算法的话主要是利用回文串的性质，回头整理好了再详细写。 #include #include #include #include #include #include #include #include #include //#include #include #include using namespace std; typedef long long LL; const int maxn=110005; const int MOD=20071027; char ori[maxn],p[maxn<<1]; int len[maxn<<1]; int main() { //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); while(~scanf(" %s",ori)) { //getchar(); int n=strlen(ori); p[0]='$'; for (int i=1;i<=n+n;i+=2) { p[i]='#'; p[i+1]=ori[i/2]; } p[2*n+1]='#'; p[2*n+2]='&'; int mx=0,po=0,ans=0; for (int i=1;i<=n+n;i++) { if(mx>i) len[i]=min(len[2*po-i],mx-i+1); else len[i]=1; while(p[i-len[i]]==p[i+len[i]])len[i]++; if(len[i]+i-1>mx) { mx=len[i]+i-1; po=i; } ans=max(ans,len[i]); } printf("%d\n",ans-1); } return 0; }
