Submission #38126429

---

Source Code Expand

#line 2 "/home/zawatin/compro/library/src/string/rollinghash.hpp"

#include <random>
#include <iostream>
#include <algorithm>
#include <string>

namespace zawa {

template <std::size_t max_length>
class rollinghash {
public:
	using hash_type = long long;

	std::random_device seed_gen;
	std::mt19937_64 mt;
	hash_type base;
	const hash_type mod = (1ULL << 61ULL) - 1;
	std::vector<hash_type> pows;

public:

	struct info {
		std::size_t len;
		hash_type hash;
		info() : len(0), hash(0) {}
		bool operator==(const info& a) {
			return len == a.len and hash == a.hash;
		}
	};

	rollinghash() : mt(seed_gen()), pows(max_length + 1, 1LL) {
		base = std::clamp((hash_type)mt() % mod, (hash_type)1e9, mod - 1);
		for (std::size_t i = 0 ; i < max_length ; i++) {
			pows[i + 1] = ((__int128_t)pows[i] * base) % mod;
		}
	}

	template <class T>
	std::vector<info> build(const std::vector<T>& A) {
		std::vector<info> res(A.size() + 1, info());	
		for (std::size_t i = 0 ; i < A.size() ; i++) {
			res[i + 1].len = i + 1;
			res[i + 1].hash = ((__int128_t)base * res[i].hash + (__int128_t)A[i]) % mod;
		}
		return res;
	}

	std::vector<info> build(const std::string& s) {
		return build(std::vector(s.begin(), s.end()));
	}

	info hash(const std::vector<info>& H, int l, int r) {
		info res = H[r];
		res.len -= H[l].len;
		res.hash -= ((__int128_t)H[l].hash * pows[r - l]) % mod;
		if (res.hash < 0) {
			res.hash += mod;
		}
		return res;
	}

	info concate(const info& h1, const info& h2) { 
		info res;
		res.len = h1.len + h2.len;
		res.hash = ((((__int128_t)h1.hash * pows[h2.len]) % mod) + h2.hash) % mod;
		return res;
	}

};

} // namespace zawa
#line 2 "ABC284f.test.cpp"

#line 6 "ABC284f.test.cpp"

int main() {
	int n; std::cin >> n;
	std::string t; std::cin >> t;
	std::string r = t;
	std::reverse(r.begin(), r.end());
	zawa::rollinghash<1000000> roll;
	auto rht = roll.build(t);
	auto rhr = roll.build(r);
	for (int i = 0 ; i < n ; i++) {
		auto f = roll.hash(rht, 0, i);
		auto c = roll.hash(rhr, n - i, 2 * n - i);
		auto b = roll.hash(rht, i + n, 2 * n);
		auto cc = roll.concate(f, b);
		if (c == cc) {
			std::cout << r.substr(n - i, n) << std::endl;
			std::cout << i << std::endl;
			return 0;
		}
	}
	std::cout << -1 << std::endl;
}

Submission Info

Judge Result