struct Manacher{//鉴于马拉车算法较复杂,此处有少量修改, //s[i]=ma[i<<1] //mp[i]表示以i为中心的最长回文串的半径,且mp[i]-1恰好为此回文串包含原字符串的字符的数量 //可以证明ma字符串所包含的回文串总数=原字符串b所包含的回文串总数+2n+2 static const int maxn=1e6+666; char ma[maxn<<1]; int mp[maxn<<1],begat[maxn];//begta[i]-> 以i开头的回文串的数量 begin at void build(char*str){ int len=strlen(str+1),l=0; ma[l++]='$';//$#.#.#.#.#.#.#.# ma[l++]='#'; for (int i=1;i<=len;i++){ ma[l++]=str[i]; ma[l++]='#'; } ma[l]=mp[l]=0; int mx=0,id=0; for (int i=0;i<l;i++){ mp[i]=mx>i ? min(mp[2 * id-i],mx-i) : 1; while(ma[i+mp[i]]==ma[i-mp[i]])mp[i]++; if (i+mp[i]>mx){ mx=i+mp[i]; id=i; } } //for(int i=2;i<=l;i++)palindrome+=mp[i]>>1;//回文串个数 //若不用dalt数组,此后可删掉 for(int i=1;i<=len;i++)begat[i]=0; for (int i=2;i<l;i++){ int s=i-mp[i]+1;//ma串最长回文左端点s s=(s+1)/2;//变为str串最长回文左端点,向上取整,因为str[i]对应smp[i<<1] int t=s+mp[i]/2-1;//右端点 begat[s]++;begat[t+1]--; } for(int i=1;i<=len+1;i++)begat[i]+=begat[i-1];//+1是为了还原 } };