算法講解

算法講解1

#include <iostream> #define maxn 10e+6; using namespace std; char s[maxn],str[maxn*2]; int p[maxn*2]; void init(char *s) {int j=0;str[0]='#';for(int i=1;i<s.length();++i){str[j++]=s[i];str[j++]='#';}str[j]='\0'; } int manacher(char *s) {init(s);int id=0;int r=-1,maxlen=0;//r最右回文半徑的位置p[0]=-1,p[1]=1;for(int i=0;i<str.length();++i){if(i<r)p[i]=min(p[2*id-i],r-i);elsep[i]=1;while(str[i-p[i]]==str[i+p[i])p[i]++;if(r<i+p[i])//更新最右的回文半徑，且當(dāng)有多個(gè)位置的最右回文半徑位置相同時(shí)只保留第一個(gè)位置出現(xiàn)的這個(gè)最右回文半徑位置r=i+p[i],id=i;maxlen=max(maxlen,p[i]-1);}return maxlen; } int main() {cin>>s;cout<<monacher(s)<<endl;return 0; }

hdu 3068 ? ?不知道tle在哪里

#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #define maxn 110005 using namespace std;char s[110005],str[110005*2]; int p[110005]; void init(char *s) {str[0]='#';int j=1;for(int i=0;i<strlen(s);++i){str[j++]=s[i];str[j++]='#';}// str[j++]=')';str[j]='\0'; } int manacher() {//p[0]=1;int r=0,id=0,len=0;for(int i=1;i<strlen(str);++i){if(i<r){p[i]=min(p[2*id-i],r-i);}elsep[i]=1;while(str[i-p[i]]==str[i+p[i]]&&i-p[i]>=0&&i+p[i]<strlen(str))p[i]++;if(r<i+id){r=i+id;id=i;}len=max(len,p[i]-1);}return len; } int main() {while(scanf("%s",s)){init(s);cout<<manacher()<<endl;}return 0; }

orzorz ?依舊tle

#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #define maxn 110010 using namespace std;char s[maxn],str[maxn*2]; int p[maxn]; /*int init(char *s) {int j=0;str[j++]='@';str[j++]='#';for(int i=0;s[i];++i){str[j++]=s[i];str[j++]='#';}str[j]='\0';return j; }*/ /*int manacher() {//p[0]=1;int r=0,id=0,len=0;int j=0;str[j++]='@';str[j++]='#';for(int i=0;s[i];++i){str[j++]=s[i];str[j++]='#';}str[j]='\0';for(int i=1;i<j;++i){if(i<r){p[i]=min(p[2*id-i],r-i);}elsep[i]=1;while(str[i-p[i]]==str[i+p[i]])p[i]++;if(r<i+id){r=i+id;id=i;}if(len<p[i]-1)len=p[i]-1;}return len; }*/ int main() {while(scanf("%s",s)!=EOF){int r=0,id=0,len=0;int j=0;str[j++]='@';str[j++]='#';for(int i=0;s[i];++i){str[j++]=s[i];str[j++]='#';}str[j]='\0';for(int i=1;i<j;++i){if(i<r){p[i]=min(p[2*id-i],r-i);}elsep[i]=1;while(str[i-p[i]]==str[i+p[i]])p[i]++;if(r<i+id){r=i+id;id=i;}if(len<p[i]-1)len=p[i]-1;}//cout<<len<<endl;printf("%d\n",len);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的manacher马拉车算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。