没有难度的模板题
我们可以直接先上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(""); } } }