HDU 3068 最长回文（ Manacher模板题）

**链接：****传送门 **

思路：Manacher模板题，寻找串中的最长回文子串

/*************************************************************************

    > File Name: hdu3068.cpp

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年05月19日 星期五 13时09分43秒

 ************************************************************************/

#include<bits/stdc++.h>

using namespace std;

const int MAX_N = 110000*3;

char s[MAX_N] , str[MAX_N];

int len1 , len2 , p[MAX_N] , ans;

// 对字符串进行预处理

void init(){

	len1 = strlen(s);

	str[0] = '$';

	str[1] = '#';

	for(int i = 0 ; i < len1 ; i++){

		str[i*2+2] = s[i];

		str[i*2+3] = '#';

	}

	len2 = len1*2 + 2;

	str[len2] = '*';

}

void Manacher(){

	int id , mx = 0;

	for(int i = 1 ; i < len2 ; i++){

		if( mx > i )	p[i] = min( p[2*id-i] , mx-i);

		else			p[i] = 1;

		for(; str[i+p[i]] == str[i-p[i]] ; p[i]++);	// 暴力匹配一下能更新的最大长度

		if( p[i] + i > mx )		mx = p[i] + i , id = i;

	}

}

int main(){

	while(~scanf("%s",s)){

		init();

		Manacher();

		ans = 0;

		for(int i = 1 ; i < len2 ; i++){

			ans = max( ans , p[i] );

		}

		printf("%d\n",ans-1);

	}

	return 0;

}

巴特西

HDU 3068 最长回文（ Manacher模板题）

最新文章

热门文章

巴特西

HDU 3068 最长回文（ Manacher模板题 ）

最新文章

热门文章

HDU 3068 最长回文（ Manacher模板题）