HDU - 3294 - Girls research(裸马拉车)

博主CSDN

题目链接

题意：

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

题解：

用manachar求出最长回文串中心和半径，因为变换后的串各字符下标改变了，所以输出原首尾下标要公式倒推
输出字符时要跳过插入的符号。如果你没有马拉车板子，或者说你不会马拉车，请见Manacher最长回文串算法

代码：

#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<iostream>
#define met(a) memset(a,0,sizeof(a));
using namespace std;
typedef long long ll;
const int maxn = 200050;
char s[maxn];
char s_new[maxn * 2];
int p[maxn * 2];
int iid = 0;
int Init(){
	int len = strlen(s);
	s_new[0] = '$';
	s_new[1] = '#';
	int j = 2;
	for (int i = 0; i < len; i++){
		s_new[j++] = s[i];
		s_new[j++] = '#';
	}
	s_new[j] = '\0';
	//printf("%s\n",s_new);
	return j;  //返回s_new的长度  
}
int Manacher(){
	int len = Init();  //取得新字符串长度并完成向s_new的转换  
	int maxLen = -1;   //最长回文长度  
	int id;
	int mx = 0;
	for (int i = 1; i < len; i++){
		if (i < mx)
			p[i] = min(p[2 * id - i], mx - i);  //需搞清楚上面那张图含义, mx和2*id-i的含义
		else
			p[i] = 1;
		while (s_new[i - p[i]] == s_new[i + p[i]])  //不需边界判断，因为左有'$',右有'\0'  
			p[i]++;
		//我们每走一步i，都要和mx比较，我们希望mx尽可能的远，这样才能更有机会执行if (i < mx)这句代码，从而提高效率 
		if (mx < i + p[i])  {
			id = i;
			mx = i + p[i];
		}
		if (p[i] - 1>maxLen){
			maxLen = p[i] - 1;
			iid = i;
		}
		// printf("%d %d %d\n",mx,id,maxLen);
	}
	/*for(int i=1;i<=len;i++)printf("%d ",p[i]);
	printf("\n");*/
	return maxLen;
}
int main(){
	char ch ;
	while (scanf("%c%s",&ch,s)!=EOF){
		getchar();
		//memset(p, 0, sizeof(p));
		int k = ch - 'a';
		for (int i = 0; s[i]; i++){
			s[i] -= k;
			if (s[i] < 'a')s[i] += 'z' - 'a' + 1;
		}
		int mx = Manacher();
		if (mx == 1)printf("No solution!\n");
		else{
			printf("%d %d\n", (iid - mx + 1)/2-1 , (iid + mx - 1)/2-1 );
			for (int i = (iid - mx + 1)/2-1; i <= (iid + mx - 1)/2-1; i++)printf("%c", s[i]);
			puts("");
		}
	}
	return 0;
}