test/rollinghash.test.cpp

• View this file on GitHub
• Last update: 2023-01-18 06:37:34+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/14/ALDS1_14_B

Depends on

• rollinghash (ロリハ) (src/string/rollinghash.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/14/ALDS1_14_B"

#include "../src/string/rollinghash.hpp"

#include <iostream>
#include <string>

int main() {
	std::string t, p; std::cin >> t >> p;
	zawa::rollinghash<1000000> roll;
	auto h1 = roll.build(t), h2 = roll.build(p);
	for (std::size_t i = 0 ; i + p.size() <= t.size() ; i++) {
		if (roll.hash(h1, i, i + p.size()) == roll.hash(h2, 0, p.size())) {
			std::cout << i << std::endl;
		}
	}
}

#line 1 "test/rollinghash.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/14/ALDS1_14_B"

#line 2 "src/string/rollinghash.hpp"

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

namespace zawa {

template <std::size_t max_length>
class rollinghash {
private:
	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 4 "test/rollinghash.test.cpp"

#line 7 "test/rollinghash.test.cpp"

int main() {
	std::string t, p; std::cin >> t >> p;
	zawa::rollinghash<1000000> roll;
	auto h1 = roll.build(t), h2 = roll.build(p);
	for (std::size_t i = 0 ; i + p.size() <= t.size() ; i++) {
		if (roll.hash(h1, i, i + p.size()) == roll.hash(h2, 0, p.size())) {
			std::cout << i << std::endl;
		}
	}
}

Back to top page