library/string/manacher.hpp

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Include: #include "library/string/manacher.hpp"

Verified with

• verify/yosupo/yosupo-enumerate_palindromes.test.cpp

Code

#pragma once

std::vector<int> manacher(std::string s) {
	std::string t = "@";
	for (auto& c : s) 
		t += c, t += '#';
	t.back() = '&';
	std::vector<int> res((int)t.size() - 1);
	int lo = 0, hi = 0;
	for (int i = 1; i < (int)t.size() - 1; i++) {
		if (i != 1)
			res[i] = std::min(hi - i, res[hi - i + lo]);
		while (t[i - res[i] - 1] == t[i + res[i] + 1])
			res[i]++;
		if (i + res[i] > hi)
			lo = i - res[i], hi = i + res[i];
	}
	res.erase(res.begin());
	for (int i = 0; i < (int)res.size(); i++)
		if ((i & 1) == (res[i] & 1))
			res[i]++;
	return res;
}

std::vector<int> manacher(std::string s) {
	std::string t = "@";
	for (auto& c : s) 
		t += c, t += '#';
	t.back() = '&';
	std::vector<int> res((int)t.size() - 1);
	int lo = 0, hi = 0;
	for (int i = 1; i < (int)t.size() - 1; i++) {
		if (i != 1)
			res[i] = std::min(hi - i, res[hi - i + lo]);
		while (t[i - res[i] - 1] == t[i + res[i] + 1])
			res[i]++;
		if (i + res[i] > hi)
			lo = i - res[i], hi = i + res[i];
	}
	res.erase(res.begin());
	for (int i = 0; i < (int)res.size(); i++)
		if ((i & 1) == (res[i] & 1))
			res[i]++;
	return res;
}

Back to top page