首页 > ACM题库 > HDU-杭电 > HDU 3294-Girls’ research-字符串处理-[解题报告]HOJ
2014
03-13

HDU 3294-Girls’ research-字符串处理-[解题报告]HOJ

Girls’ research

问题描述 :

One day, sailormoon girls are so delighted that they intend to research about palindromic strings. Operation contains two steps:
First step: girls will write a long string (only contains lower case) on the paper. For example, "abcde", but ‘a’ inside is not the real ‘a’, that means if we define the ‘b’ is the real ‘a’, then we can infer that ‘c’ is the real ‘b’, ‘d’ is the real ‘c’ ……, ‘a’ is the real ‘z’. According to this, string "abcde" changes to "bcdef".
Second step: girls will find out the longest palindromic string in the given string, the length of palindromic string must be equal or more than 2.

输入:

Input contains multiple cases.
Each case contains two parts, a character and a string, they are separated by one space, the character representing the real ‘a’ is and the length of the string will not exceed 200000.All input must be lowercase.
If the length of string is len, it is marked from 0 to len-1.

输出:

Input contains multiple cases.
Each case contains two parts, a character and a string, they are separated by one space, the character representing the real ‘a’ is and the length of the string will not exceed 200000.All input must be lowercase.
If the length of string is len, it is marked from 0 to len-1.

样例输入:

b babd
a abcd

样例输出:

0 2
aza
No solution!

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=3294

字符串————

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

typedef __int64 LL;
const int N=400109;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

char xh[N],s[N],pi[26];
int p[N],len;

void manacher(char *str)
{
	int mx=0;//记录前面回文串最长影响到的地方。不一定是最长回文串造成的。
	int id;//最长影响串的id
	int ans=0,t;//最长结果
	for(int i=1;i<len;i++)
	{
		if(mx>i)    p[i]=min(p[2*id-i],mx-i);
		else	p[i]=1;
		while(str[i+p[i]]==str[i-p[i]])
		{
            p[i]++;
		}
		if(i+p[i]>mx)
		{
			mx=i+p[i];
			id=i;
		}
		if(p[i]>ans)	ans=p[i],t=i;
	}
	ans--;
	if(ans<2)
	{
	    printf("No solution!\n");
	    return ;
	}
	int j=t-(ans-1);
	printf("%d %d\n",j/2-1,j/2+ans-2);
	for(int i=0;i<ans;i++,j+=2)
        printf("%c",pi[str[j]-'a']);
    printf("\n");
}

int main()
{
    int i,j,l;
    char c,a;
	while(scanf("%c%s",&c,s)!=EOF)
	{
	    l=c-'a';
	    for(i=0;i<26;i++)
            pi[i]=(i+26-l)%26+'a';
	    getchar();//这个地方要注意
        len=strlen(s);
        xh[0]='$';xh[1]='#';
        for(i=0,l=2;i<len;i++,l+=2)
        {
            xh[l]=s[i];
            xh[l+1]='#';
        }
        len=len*2+2;
		manacher(xh);
	}
	return 0;
}

参考:http://blog.csdn.net/xh_reventon/article/details/9424591


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?