poj3974 manacher算法,最大回文子串

2017-05-22 97点热度 0人点赞

Sample Input

abcbabcbabcba
abacacbaaaab
END

Sample Output

Case 1: 13
Case 2: 6

就是裸的求最大回文字串

//$#a#a#a#b#
#include
#include
#include
using namespace std;
const int mx=1000000+100;
int p[2*mx],len;
char s[2*mx];
int main(){
	int T=1;
	while(~scanf("%s",s)&&strcmp(s,"END")!=0){
		len=strlen(s);
		//插入"#"
		for(int i=len;i>=0;i--){
			s[i*2+1]='#';
			s[i*2+2]=s[i];
		}
		s[0]='$';
		len=2*len+1;
		int id=0,mx=0;
		p[0]=p[1]=1;
		for(int i=2;imx) mx=p[i];
			if(i+p[i]>id+p[id]) id=i;
		}
		printf("Case %d: %dn",T++,mx-1);
	}
	return 0;
}

未经允许不得转载!poj3974 manacher算法,最大回文子串

本文地址:https://ai.52learn.online/568

站长邮箱:ai52learn@foxmail.com