前言:补博Manachar
1.定义Manacher用于求字符串中任意pos为中心一起向左向右扩展的回文串长度.特别的时每个字符都被认为是自己的回文串.也就是说对于表示此长度的p数组初始值为1.
2.p数组的求解
相区别于kmp的nxt数组,Manaher的p数组表示p[ i ] = k时, 有 p[ i -k + 1 ] = p[ i + k - 1] , p [ i - k + 2 ] = p [ i + k -2 ]. . .p[ i ]= p[ i ],包括它自身的 k 次 字符匹配,即回文串.特别的我们定义p[ 0 ]=1.那怎么求解p数组呢?类比于求kmp的nxt数组,我们知道 p[ 0 ],p[1],p[ 2 ]..p [ n-1],求 p [n].不妨设 0 ... n-1 中 存在 id 使 p[ id ]+id-1有最大值 , 将这个右端点我们定义为 right = p[ id ] + id -1 ,左端点为 left = id - p[id] +1.对于当前 n .如果 n< = right,那么我们一定能在[ left,id]中找都 n',且p[n']已求出来了.如果 p[n']+n-1<=right,那么根据回文串的对称性可知 p[n]=p[n'],那如果 n+p[ n']-1>right.那么p [ n ]=right- n+1.为什么 ? 因为 n'-p [n']+1<left 时, p [n]+n-1一定小于right.因为大于 right就于right的最大回文长度的定义相违背了. 如果 n>right,那么我们只能根据回文串的定义暴力求解.附上LGmanacher的板子.
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 using namespace std; 6 #define e exit(0) 7 #define R register 8 #define ll long long 9 const int maxn=11000000+10; 10 char s[maxn<<1],t[maxn<<1]; 11 long long lens,lent,ans=-1,p[maxn<<1]; 12 void manachar() 13 { 14 long long mid=0,right=0; 15 p[0]=1; 16 for(R ll i=1;i<lens;++i){ 17 p[i]=i<=right?min(right-i+1,p[mid*2-i]):1; 18 while(s[i-p[i]]==s[i+p[i]]&&i-p[i]>=0&&i+p[i]<=lens) 19 ++p[i]; 20 if(p[i]+i-1>right){ 21 right=p[i]+i-1; 22 mid=i; 23 } 24 } 25 } 26 int main() 27 { 28 // freopen("s.in","r",stdin); 29 // freopen("s.out","w",stdout); 30 scanf("%s",t+1); 31 lent=strlen(t+1); 32 lens=lent*2+1; 33 for(R ll i=0;i<lens;++i) 34 { 35 if(i==0) 36 s[i]='#'; 37 else if(i&1) 38 s[i]=t[(i+1)/2]; 39 else s[i]='#'; 40 } 41 manachar(); 42 for(R ll i=0;i<lens;++i) 43 ans=max(p[i]-1,ans); 44 printf("%lld",ans); 45 return 0; 46 }