变形的求最大回文子串，要求输出两个端点。
我觉得把'b'定义为真正的'a'是件很无聊的事，因为这并不会影响到最大回文子串的长度和位置，只是在输出的时候设置了一些不必要的障碍。
另外要注意一下原字符串s1中的字符在预处理以后的字符串s2中对应的坐标关系，这样输出的时候就可以照着这个关系转化。
轻松1A，嘿嘿
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; const int maxn = + ;
char s1[maxn], s2[maxn * ], real;
int p[maxn * ]; void init(char s1[], char s2[])
{
int j = ;
s2[] = '$', s2[] = '#';
for(int i = ; s1[i] != '\0'; ++i)
{
s2[j++] = s1[i];
s2[j++] = '#';
}
s2[j] = '\0';
} void manacher(char s[])
{
p[] = ;
int id, mx = ;
for(int i = ; s[i] != '\0'; ++i)
{
if(mx > i)
p[i] = min(p[id*-i], mx-i);
else
p[i] = ;
while(s[i + p[i]] == s[i - p[i]])
++p[i];
if(i + p[i] > mx)
{
id = i;
mx = i + p[i];
}
}
} char change(char c)
{
c -= real - 'a';
if(c < 'a') c += ;
if(c > 'z') c -= ;
return c;
} void getans(void)
{
int mlen = , pos;
for(int i = ; s2[i] != '\0'; ++i)
{
if(p[i] - > mlen)
{
mlen = p[i] - ;
pos = i;
}
}
if(mlen == )
printf("No solution!\n");
else
{
int L = (pos - (p[pos] - )) / - ;
int R = (pos + (p[pos] - )) / - ;
printf("%d %d\n", L, R);
for(int i = L; i <= R; ++i)
printf("%c", change(s1[i]));
printf("\n");
}
} int main(void)
{
#ifdef LOCAL
freopen("3294in.txt", "r", stdin);
#endif while(scanf("%c", &real) == )
{
scanf("%s", s1);
getchar();
init(s1, s2);
manacher(s2);
getans();
}
return ;
}
代码君