Girls' research HDU - 3294

没有难度的模板题

我们可以直接先上Manacher
然后就能够找到最长的回文子串

然后我们对字串进行解码
如何进行解码？
巧妙地利用取模。试几次就出来了

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int max_n = 2e5+100;

void Manacher(char s[],int d[],char ts[]){
    int n = strlen(s);
    fill(d,d+n*2+10,1);
    for (int i=0,j=0;i<n;++i){
        ts[j++]='#';ts[j++]=s[i];
    }int m = n*2+1;
    ts[m-1]='#';ts[m]='\0';
    for (int i=0,j=-1,t=0;i<m;++i){
        if (j>=i)d[i]=min(j-i+1,d[(t<<1)-i]);
        while (i+d[i]<m&&i-d[i]>=0&&ts[i+d[i]]==ts[i-d[i]])++d[i];
        if (i+d[i]>j)j=i+d[i]-1,t=i;
    }
}
char s[max_n],ts[max_n<<1];
int d[max_n<<1];
char ch;
int main(){
    while (~scanf("\n%c %s",&ch,s)){
        Manacher(s,d,ts);
        int n = strlen(ts);
        int l=0;int len = 0;
        for (int i=1;i<n;++i){
            int dist = ((d[i]<<1)-1)>>1;
            if (dist>len){
                len = dist;
                if (i&1){
                    l = (i>>1)-len/2;
                }
                else l = ((i-1)>>1)-len/2+1;
            }
        }
        if (len < 2){
            printf("No solution!\n");
        }
        else {
            int k = ch-'a';
            printf("%d %d\n",l,l+len-1);
            for (int i=l;i<l+len;++i)printf("%c",(char)((s[i]-ch+26)%26+'a'));
            puts("");
        }
    }
}