verify/yosupo/yosupo-enumerate_palindromes.test.cpp

View this file on GitHub
Last update: 2022-07-21 16:12:33-04:00
Problem: https://judge.yosupo.jp/problem/enumerate_palindromes

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/string/manacher.hpp"

int main() {
	std::ios_base::sync_with_stdio(0);
	std::string s; std::cin >> s;
	std::vector<int> ans = manacher(s);
	for (int &x : ans)
		std::cout << x << " ";
	std::cout << '\n';
	return 0;
}

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

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;
}

int main() {
	std::ios_base::sync_with_stdio(0);
	std::string s; std::cin >> s;
	std::vector<int> ans = manacher(s);
	for (int &x : ans)
		std::cout << x << " ";
	std::cout << '\n';
	return 0;
}