最长回文

以前有曾经遇过回文问题  但是怎末写都TLE （哭哭
结果是今天看到的这一篇BLOG交会我的
 http://my.oschina.net/pathenon/blog/63575
做法就是以其中一点为中心找出他最大回文的半径
所以像ASDSA
找到以D（str[3])为中心的最大半径是3 然后他后面的S(str[4])位置是4< 3+3(半径）-1 , 因此可以不用重复计算他的回文半径 因为他跟前面那个S（str[2]）是对称的 所以可以直接套用
如果有找到新的最大半径 则要记得更新哦
答案就是最大回文半径*2-1～～
附上code 但因为是看的当参考的 所以应该跟blog上的很雷同

	#include<iostream>
	#include<cstdio>
	#include<cstring>
	using namespace std;
	#define max 110010 * 2
	int main(){
	char ch[max],pre[max];
	int ans[max];
	while(scanf("%s",ch)!=EOF){
	int length = strlen(ch);
	pre[0] = '#';
	pre[1] = '#';
	for(int i=0;i<length;i++){
	pre[i*2+2] = ch[i];
	pre[i*2+3] = '#';
	}
	int n = length*2+2;
	//memset(ans,0,sizeof(int));
	/**
	ans:以pre[i]为中心的最长回文串的半径为ans[i]。
	idx:已经找出的能够右延伸最远距离的回文子串的起始位置。
	m:已经找出的能够右延伸最远距离的回文子串的结束位置。
	**/
	pre[n] = '0';
	int idx = 0,m = 0;
	for(int i=1;i<n;i++){
	if(m>i) ans[i] = ans[idx*2-i] < (m-i)?ans[idx*2-i] : (m-i);
	else ans[i] = 1;
	for(; pre[i + ans[i]]==pre[i - ans[i]]; ans[i]++);
	if(ans[i] + i > m)
	{
	m = ans[i] + i;
	idx = i;
	}
	}
	int t = 0;
	for(int i=2;i<n;i++){
	if(ans[i]>t) t = ans[i];
	}printf("%d\n",t-1);
	}
	}

view raw gistfile1.cpp hosted with ❤ by GitHub