Manacher算法
Manacher算法？？？
Mancher算法是用来找最大回文串的，因为功能太过单一，所以用处不是很多，但是在找回文串方面还是很强大的。
大致原理：
枚举回文串的中点，用p[i]表示以i为中心的最大回文串的长度。然后对p[i]进行扩展就可以了。
最简单的扩展就是当s[i+p[i]+1]=s[i-p[i]-1]的时候p[i]就可以加一。
然后就是对上面进行一下优化，用一个id来记录可以延伸的最靠右的回文串的中心，mx为其长度。然后对于枚举到的中心i如果i没有超过id+mx,说明在id前面一定有一个j与i相同，并且j已经处理过了，所以就可以直接将p[i]=p[j]但是需要注意的是，如果i+p[j]超出了mx，就不能保证这是个回文串了，p[i]=min(p[id-(i-id)],mx-i) 这里的id-(i-id)就是上面的j
同时不断地更新id和mx并且记录下最大的p[i]就行了。
一道板子题：luogu3805
代码：
1 #include<vector> 2 #include<queue> 3 #include<ctime> 4 #include<algorithm> 5 #include<deque> 6 #include<cstdlib> 7 #include<string> 8 #include<cstring> 9 #include<map> 10 #include<bitset> 11 #include<cstdio> 12 #include<iostream> 13 #define max(x,y) x>y?x:y 14 using namespace std; 15 typedef long long LL; 16 void read(int &x){ 17 x=0;int f=1;char c=getchar(); 18 while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();} 19 while(c>='0'&&c<='9') { x=x*10+c-'a';c=getchar();}x*=f; 20 } 21 const int N=11000000+10; 22 char s[N],S[N*2]; 23 int ans,len,id,mx,p[N*2]; 24 inline void manacher() 25 { 26 for(int i=1;i<=len;++i) 27 { 28 if(id+mx>i) 29 p[i]=min(id+mx-i,p[id*2-i]); 30 while(i+p[i]+1<=len&&i-p[i]-1>=1&&S[i+p[i]+1]==S[i-p[i]-1]) p[i]++; 31 if(i+p[i]>id+mx) id=i,mx=p[i]; 32 ans=max(ans,p[i]); 33 } 34 printf("%d",ans); 35 } 36 37 int main() 38 { 39 cin>>s; 40 int l=strlen(s); 41 S[++len]='#'; 42 for(int i=0;i<l;++i) 43 { 44 S[++len]=s[i]; 45 S[++len]='#'; 46 } 47 manacher(); 48 49 return 0; 50 }
查看16道真题和解析
