题目描述

给我们一个字符串s,对s的每个位置,让我们求出以该位置结尾的回文子串个数.
其中,除了s的第一个字符,后面的字符都是经过加密的.
具体地，若第 i(i>=1) 个位置的答案是 k，第 i+1 个字符读入时的 ASCII 码为 c,则第 i+1 个字符实际的 ASCII 码为 (c-97+k)%26+97.所有字符在加密前后都为小写字母.

样例

输入

debber

输出

1 1 1 2 1 1

分析

PAM模板题,求以一个位置结尾的回文子串个数就是求以这个位置结尾的最长回文子串的border数.

PAM

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int tr[N][26],idx,last,tot;
int len[N];
int fail[N],level[N];//level表示u位于第几层 
char s[N];
int node(int x){
    len[idx++]=x;
    return idx-1;
}
void init(){
    idx=tot=0;
    node(0);
    node(-1);
    fail[0]=1,fail[1]=0;
    level[0]=level[1]=0;
    last=0;
}
int get_fail(int x){
//  cout<<"last="<<last<<endl;
    while(s[tot-len[x]-1]!=s[tot]){
    //  cout<<x<<endl;
        x=fail[x];
    }
    return x;
}
void insert(char c){
    s[++tot]=c;
    int now=get_fail(last);
    if(!tr[now][c-'a']){
        int x=node(len[now]+2);
        int t=get_fail(fail[now]);
        fail[x]=tr[t][c-'a'];
        level[x]=level[fail[x]]+1;
        tr[now][c-'a']=x;

    }
    last=tr[now][c-'a'];
    cout<<level[last]<<" ";
}
int main(){
    cin>>s+1;
    init();
    for(int i=1;s[i];i++){
        if(i>1)s[i]=(s[i]-97+level[last])%26+97;
        insert(s[i]);
    }
    return 0;
}