manacher

用途

$ O(n)求最长回文串 $

思路

• 在字符串前面加$#,后面加^,相邻字符之间添加#
• 可以发现原字符串的回文串都会转换为新字符串的奇数回文串
• 并且原回文串长度=新回文串半径-1
• $ 定义p_i为以i为中心的回文串的半径 $
• $ 假设已经找出一个回文串,中心为mid,mr为该半径+1 $
• $ 若i<mr ,代表当前段在已经找到的回文串内 $
  • $ 找出相对于mid对称的点j=2*mid-i ,p_j已知$
  • $ 则p_i=min(p_j,mr-i) 不能超过当前大的回文串长度(超过的段无法保证回文，没超过则P_i=p_j)$
• $ 暴力更新p_i长度 $
• $ 若i+p_i>mr 更新mid和mr $

  string a,s;
  int p[N],n;
  void init(){
    s="";
    s+="$#";
    for(auto c:a)s+=c,s+='#';
    s+="^";
    n=s.size();
  }
  void manacher(){
    int mr=0,mid;
    for(int i=1;i<n;i++){
        if(i<mr)p[i]=min(p[2*mid-i],mr-i);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]])p[i]++;
        if(i+p[i]>mr){
            mr=i+p[i];
            mid=i;
        }
    }
  }
  void solve(){
    cin>>a;
    init();
    manacher();
    int res=0;
    for(int i=1;i<n;i++)res=max(res,p[i]-1);
    cout<<res;
  }
  

  P1659 [国家集训队] 拉拉队排练

  题意

  给定一字符串,求出所有回文串,对奇数长度排序从大到小,求前k个奇数回文串长度的乘积

  思路

  manacher预处理，注意是所有回文串不是每个最长回文串
  倒数枚举，累计求和，快速幂计算，因为如果有cnt[n]个最长回文串，则cnt[n-2],cnt[n-4]…都应加上未算的cnt[n]

  string a,s;
  ll n,k,p[N],cnt[N];
  void init(){
    s="";
    s+="$#";
    for(auto c:a)s+=c,s+='#';
    s+="^";
    n=s.size();
  }
  void manacher(){
    int mr=0,mid;
    for(int i=1;i<n;i++){
        if(i<mr)p[i]=min(p[2*mid-i],1ll*mr-i);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]])p[i]++;
        if(i+p[i]>mr){
            mr=i+p[i];
            mid=i;
        }
        if(p[i]%2==0)cnt[p[i]-1]++;
    }
  }
  ll qpow(ll a,ll b){
    ll ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
  }
  void solve(){
    cin>>n>>k>>a;
    init();
    manacher();
    ll res=1,sum=0;
    for(int i=n;i>=1;i--){
        if(i%2==0)continue;
        sum+=cnt[i];
        if(k>=sum){
            res=res*qpow(i,sum)%mod;
            k-=sum;
        }
        else{
            res=res*qpow(i,k)%mod;
            k=0;
            break;
        }
    }       
    if(k>0){
        cout<<"-1\n";
        return;
    }
    cout<<res;
  }