Girls' research HDU

题目链接

题意：通过第一个字符与a的关系翻译字符串，输出最长回文串和首尾下标，不存在则输出No solution!

思路：马拉车算法记录修改串的最长半径和下标。然后反推原串的起点到终点。

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<map>
#include<algorithm>
#define N 200060
#define ll long long
using namespace std;
const int maxn=2000110;
char a[maxn],text[maxn];
int P[maxn];
int ans;
int pos;
void pre_treat(){
    int len = strlen(a);
    for(int i=0;i<len;i++){
        text[i*2] = '#';
        text[i*2+1] = a[i];
    }
    text[len*2]='#';text[len*2+1]='';
}
void manacher(){
    P[0] = 1;                                   //第一个字符的回文串肯定是1
    int len = strlen(text);
    int md = 0;
    for(int i=1;i<len;i++){
        if(i<md+P[md]){
            int k = P[md*2-i];                  //找到对称点的回文串长度
            if(i+k<md+P[md]) P[i] = k;          //回文串没有超过右界
            else{
                k = md+P[md]-i;
                while(i+k<len&&i+k>=0&&text[i+k]==text[i-k]) k++;
                md = i;
                P[i] = k;
            }
        }
        else{
            int k = 1;
            while(i+k<len&&i+k>=0&&text[i+k]==text[i-k]) k++;
            md = i;
            P[i] = k;
        }
        if(ans<P[i]&&P[i]-1>=2)
        {
            ans=P[i];
            pos=i;
        }
    }
  // for(int i=0;i<len;i++) printf("%d ",P[i]);      //(处理之后的每个点的回文串的长度)/2+1
   // printf("
");
}
int main()
{
    char b[10];
    while(~scanf("%s%s",b,a))
    {
        char x=b[0];
        int n=strlen(a);
        for(int i=0;i<n;i++)
        {
            int xx=a[i]-x;
            xx+=26;
            xx%=26;
            a[i]='a'+xx;
        }
        ans=0;
        pos=0;
        for(int i=0;i<=2*n+1;i++)
        {
            P[i]=0;
        }
        pre_treat();
        manacher();
    //    printf("%s
",text);
        //printf("ans:%d pos:%d P:%d
",ans,pos,P[pos]);
        if(ans==0)
        {
            printf("No solution!
");
        }
        else
        {
              int len=P[pos]-1;
              int r=(pos+P[pos]-1)/2-1;
              int l=r-len+1;
            printf("%d %d
",l,r);
            for(int i=l;i<=r;i++)
            {
                printf("%c",a[i]);
            }
            puts("");
        }
    }
}