题解：P4324 [JSOI2016] 扭动的回文串

现有题解好像都带个

\log

，这里给个线性时间解法。前两种情况用Manacher算法可以直接做到线性，因此主要关注第三种情况。

可以注意到如下性质：存在某个最长扭动回文串，其 $AB$ 分界线到回文中心的距离等于回文中心在原串中的最长回文半径。

证明是直观的：任意考虑一个最长扭动回文串，如果它已经满足这一性质，则结束，否则不妨设回文中心在

A

中。将分界线不断地向右移动，可以发现只要不移出最长回文半径的范围，得到的串就不会改变，因此可以一直把分界线移到最长回文半径处，得到一个最长且满足性质的扭动回文串。

上述性质说明可以通过扩展极长回文子串的方式得到答案，由此得到一个

O(n\log{n})

的做法，即枚举每个回文中心，以最长回文半径为下界做二分，用字符串哈希判断是否回文。

为了消掉

\log

，可以维护当前已知的最大长度，枚举回文中心时先对最大长度加一用字符串哈希

O(1)

时间判断一下，如果不回文说明不可能更优，如果回文就逐字符扩展，直到不回文，稍微分析一下就会发现这部分用时是线性的。

核心代码如下：

CPP

int solve(const string& a, const string& b) {
	int n = a.length();
	string aa("#"), raa("#"), rbb("#");
	for (int i = 0; i < n; i++) {
		aa += a[i];
		aa += '#';
		raa += a[n - i - 1];
		raa += '#';
		rbb += b[n - i - 1];
		rbb += '#';
	}
	n = 2 * n + 1;
	auto man = manacher(aa);
	str_hash hash(aa), hrash(raa), hrbsh(rbb);
	int mx = 1;
	for (int i = 1; i < n; i++) {
		mx = max(mx, man[i]);
		if (i + mx >= n)
			continue;
		auto lh = hash.substr_hash(i - mx, i);
		auto rhl = hrash.substr_hash(n - i - man[i] - 1, n - i - 1), rhr = hrbsh.substr_hash(n - i - mx + 1, n - i - man[i]);
		pair<int, int> rh{ (rhl.first + 1LL * rhr.first * hash.pow1[man[i] + 1] % mod1) % mod1,(rhl.second + 1LL * rhr.second * hash.pow2[man[i] + 1] % mod2) % mod2 };
		if (lh.first != rh.first || lh.second != rh.second)
			continue;
		int d = mx + 1;
		while (i - d >= 0 && n - i - d + 1 >= 0 && aa[i - d] == rbb[n - i - d + 1])
			d++;
		mx = max(mx, d - 1);
	}
	return mx;
}
int main() {
	read<int>();
	string a, b;
	cin >> a >> b;
	auto ra = a, rb = b;
	reverse(ra.begin(), ra.end());
	reverse(rb.begin(), rb.end());
	cout << max(solve(a, b), solve(rb, ra));
	return 0;
}

题解：P4324 [JSOI2016] 扭动的回文串

文章操作

相关推荐

评论

题解：P4324 [JSOI2016] 扭动的回文串