Rockdu's Blog

Description

全部由小写字母构成且长度不超过 100000 的非空字符串，求最长的连续子字符串
使得该字符串与其反转字符串相等

Input

输入包含多组测试数据，每组数据一行，为一个长度不超过 100000 的非空字符串

Output

每组数据输出一行，为最长的连续子字符串的长度

Sample Input

abcbad
abccba
abcba
abbacc
ccabba

Sample Output

5
6
5
4
4

根据今天连WA带TLE的经验可以归纳出在写Manacher的时候需要注意这几点：

    1、不同case之间要清零清干净

    2、位运算的优先级低于加减乘除…………

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e5 + 5;
int RL[maxn << 1], cnt, mx;
char s[maxn << 1], r[maxn];

void Manacher() {
	int Mr = 0, Mpos = 0;
	int len = cnt;
	for(register int i = 0; i < len; ++i) {
		if(i <= Mr) {
			RL[i] = min(RL[(Mpos << 1) - i], Mr - i); //记得位运算
			for(; i - RL[i] >= 0 && i + RL[i] <= len && s[i - RL[i]] == s[i + RL[i]]; ++RL[i]);
			--RL[i];
			if(Mr < RL[i] + i) Mr = i + RL[i], Mpos = i;
		}else {
			for(; i - RL[i] >= 0 && i + RL[i] <= len && s[i - RL[i]] == s[i + RL[i]]; ++RL[i]);
			--RL[i];
			Mr = i + RL[i], Mpos = i;
		}
		mx = max(mx, RL[i]);
	}
}

int main() {
	while(scanf("%s", r) != -1) {
		cnt = mx = 0;
		int mxr = strlen(r);
		for(register int i = 0; i < mxr; ++i)
			{s[cnt++] = '#', s[cnt++] = r[i];}
		s[cnt++] = '#';
		Manacher();
		printf("%d\n", mx);
		memset(RL, 0, sizeof(RL));
	}
	return 0;
}