L2-008 最长对称子串（马拉车 or 技巧暴力）

题目链接

https://pintia.cn/problem-sets/994805046380707840/problems/994805067704549376

思路 法一

因为要求的是最长的对称子串，其实就是求最长回文子串，我们很容易就能和马拉车算法联系起来，由于这里数据比较水所以直接套板子就能过，如果没学过马拉车的话可以带一点技巧的暴力过去

法二

对于一个回文串，要么是奇数长度要么是偶数长度，那么我们只需要枚举中心位置以及回文半径即可，复杂度是 O ( N 2 ) O(N^2) O(N2)

法三

我们提前用字符串hash处理，然后同样是枚举回文中心以及回文半径

代码 马拉车

#include
using namespace std;
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f

#define N 210005

char S[N],str[N*2+5];
int len1,len2,ans,p[N*2+5];

void init() {//数组初始化，即数组长度翻倍 
	str[0] = '$';//为了防止数组越界 
	str[1] = '#';
	for(int i = 0; i i?min(p[id*2-i],m-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()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin.getline(S,N-1);
	len1 = strlen(S);
	manacher();
	int maxlen = 0;
	for(int i = 0; i