Manacher练习

洛谷P1659 [国家集训队]拉拉队训练

艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。

拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队加油助威。

一个阳光明媚的早晨，雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行，每个人手中都举了一个写有26个小写字母中的某一个的牌子，在比赛的时候挥舞，为小伙子们呐喊、加油。

雨荨发现，如果连续的一段女生，有奇数个，并且他们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。

现在雨荨想找出所有和谐小群体，并且按照女生的个数降序排序之后，前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大，雨荨只要你告诉她，答案除以19930726的余数是多少就行了。

思路

直接用 $\mathrm{Manacher}$ ，过程中统计长度的个数，最后利用前缀和的思想倒序统计（因为长的回文子串肯定包括短的回文子串）。

由于 $k$ 较大，所以需要快速幂。

时间复杂度 $O(n)$ 。

代码

#include<bits/stdc++.h>
#define ll long long 
#define N 1000010
#define mod 19930726

using namespace std;

inline ll read() {
    ll w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n;
char a[N],s[N<<1];
ll k,P[N<<1],ans=1,cnt[N];

ll qpow(ll x,ll y) {
    if(!y) return 1;
    ll t=qpow(x,y>>1);
    t=t*t%mod;
    if(y&1) return t*x%mod;
    return t;
}

void change() {
    int m=0;
    s[m++]='$',s[m++]='#';
    for(int i=0;i<n;i++) s[m++]=a[i],s[m++]='#';
    s[m++]='&';
    n=m;
}

void Manacher() {
    ll R=0,C;
    for(int i=1;i<n;i++) {
        if(i<R) P[i]=min(P[(C<<1)-i],R-i);
        else P[i]=1;
        while(s[i+P[i]]==s[i-P[i]]) P[i]++;
        if(i+P[i]>R) {
            R=i+P[i];
            C=i;
        }
        cnt[P[i]-1]++;
    }
}

int main() {
    n=read(),k=read();
    scanf("%s",a);
    change();
    Manacher();
    ll sum=0;
    for(int i=n/2;i>=1;i--) {
        if(i%2==0) continue;
        sum+=cnt[i];
        (ans*=qpow(i,min(k,sum)))%=mod;
        k-=sum;
        if(k<=0) break;
    }
    if(k>0) printf("-1\n");
    else printf("%lld\n",ans);
    system("pause");
    return 0;
}

---

洛谷P4555 [国家集训队]最长双回文串

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为abc，逆序为cba，不相同）。

输入长度为 $n$ 的串 $S$ ，求 $S$ 的最长双回文子串 $T$ ，即可将 $T$ 分为两部分 $X$ ， $Y$ ，（ $|X|,|Y|≥1$ ）且 $X$ 和 $Y$ 都是回文串。

思路

$\mathrm{Manacher}$ 算法中，变换后的字符串，对于以每个字符为中心的最长回文串，其端点一定落在 # 上。

定义 $lm[i],rm[i]$ 分别表示以 $i$ 为左端点，右端点的最长回文子串的长度。

在进行 $\mathrm{Manacher}$ 算法的过程中，若已经求出了 $P[i]$ ，那么该回文子串的左右端点分别为 $i-P[i]+1$ 和 $i+P[i]-1$ （回文子串长度为 $P[i]-1$ ）。于是便可以在进行 $\mathrm{Manacher}$ 的过程中把 $lm,rm$ 给求出来。

但是还有个问题，上面只求出了每个中心的 “最长” 回文子串的左右端点对应的 $lm,rm$ ，有可能其他中心的非最长比其值要长，所以还需要再 $O(n)$ 递推。

对于 $lm$ ，每次向后移动一个 # ，其长度可能减 $2$ ，即 lm[i]=max(lm[i],lm[i-2]-2) ，直接顺推即可。

对于 $rm$ ，每次向前移动一个 # ，其长度可能减 $2$ ，即 rm[i]=max(rm[i],rm[i+2]-2) ，直接逆推即可。

最终最大的 $lm[i]+rm[i]$ 即为答案。

注意可以为答案的前提是 $lm[i]$ 和 $rm[i]$ 都不为 $0$ 。

代码

#include<bits/stdc++.h>
#define N 100010

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

char a[N],s[N<<1];
int n,P[N<<1],lm[N<<1],rm[N<<1],ans=0;

void change() {
    n=strlen(a);
    int m=0;
    s[m++]='$',s[m++]='#';
    for(int i=0;i<n;i++) s[m++]=a[i],s[m++]='#';
    s[m++]='&';
    n=m;
}

void Manacher() {
    int R=0,C;
    for(int i=1;i<n;i++) {
        if(i<R) P[i]=min(P[(C<<1)-i],R-i);
        else P[i]=1;
        while(s[i+P[i]]==s[i-P[i]]) P[i]++;
        if(i+P[i]>R) {
            R=i+P[i];
            C=i;
        }
        int l=i-P[i]+1,r=i+P[i]-1;
        lm[l]=max(lm[l],P[i]-1);
        rm[r]=max(rm[r],P[i]-1);
    }
}

int main() {
    scanf("%s",a);
    change();
    Manacher();
    for(int i=3;i<n;i+=2) lm[i]=max(lm[i],lm[i-2]-2);
    for(int i=n-1;i>=1;i-=2) rm[i]=max(rm[i],rm[i+2]-2);
    for(int i=1;i<n;i+=2) if(lm[i]&&rm[i]) ans=max(ans,lm[i]+rm[i]);
    printf("%d\n",ans);
    system("pause");
    return 0;
}