笔记

Manacher算法

学习了一下马拉车算法, 发现它很有趣. # 描述 先在字符之间和字符串首末加'#' (原串中未出现的某字符), 使长度为n的原串扩充到(2n+1), 统一奇偶回文串.

算法从左向右扫描新串. 设当前处理i号字符.

令f[i]=以i为中心的最长回文半径 (不含i本身), mx = max{ k+f[k] | k<i }, mx = j+f[j] (j<i). 分两类考虑:

  1. mx ≥ i 如图, 绿色部分是回文子串. i'是i关于j的对称点. 将f[i]初始化为 min{ mx-i, f[i'] }, 进行扩展. Manacher

  2. mx < i 将f[i]初始化为0, 进行扩展.

得到f[i]后, 更新mx和j.

如果新串位置i为'#', 则原串对应位置有一个长度为f[i]的偶回文串. 如果新串位置i为原始字符, 则原串对应位置有一个长度为f[i]的奇回文串.

时间复杂度

只有情况1, 当 f[i']<mx-i 时, 扩展时会检查先前访问过的位置. 然而, 在这种情形下, f[i] = f[i'], 检查之后发现无法继续扩展, 不再循环.

其余情况, 总是检查先前没有访问过的位置.

综上, 时间复杂度为线性.

代码

hihoCoder #1032: 最长回文子串 

const int N = 1e6;
int f[2*N + 1];
char s[N+1];

void manacher(char s[], int n)
{
	static char t[2*N + 1];
	rep (i, 0, n) {
		t[i*2] = '#';
		t[i*2+1] = s[i];
	}
	t[2*n] = '#';

	int j = -1, mx = -1;
	rep (i, 0, 2*n + 1) {
		f[i] = mx > i ? min(mx-i, f[2*j-i])+1 : 1;
		while (i >= f[i] && i + f[i] <= 2*n && t[i+f[i]] == t[i-f[i]]) ++f[i];
		if (i + --f[i] > mx) {
			mx = i + f[i];
			j = i;
		}
	}
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%s", s);
		int n = strlen(s);
		manacher(s, n);
		printf("%d\n", *max_element(f, f+2*n+1));
	}
	return 0;
}