test/string/rolling_hash/aoj_alds1_14_b.test.cpp

• View this file on GitHub
• Last update: 2024-10-12 19:20:45+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/14/ALDS1_14_B

Depends on

• Rolling Hash (src/string/rolling_hash.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/14/ALDS1_14_B

#include "src/string/rolling_hash.hpp"

#include <iostream>
#include <string>

using namespace std;

int main() {
	string t, p;
	cin >> t >> p;
	int n = p.size();

	RollingHash rht, rhp;
	rht.build(t);
	rhp.build(p);
	for (int i = 0; i <= (int)t.size() - n; ++i)
		if (rht.find(i, i + n) == rhp.find(0, n)) cout << i << endl;

	return 0;
}

#line 1 "test/string/rolling_hash/aoj_alds1_14_b.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/14/ALDS1_14_B

#line 1 "src/string/rolling_hash.hpp"



#include <algorithm>
#include <chrono>
#include <cstdint>
#include <random>
#include <string>
#include <vector>

class RollingHash {
private:
	static std::uint64_t const MOD = (1ULL << 61) - 1;

	static std::uint64_t generate_base() noexcept {
		std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count());
		std::uniform_int_distribution<std::uint64_t> rand(1, MOD - 1);
		return rand(mt);
	}

	static inline std::uint64_t base = generate_base();
	static inline std::vector<std::uint64_t> power;

	static void extend_power(int n) {
		if ((int)power.size() >= n + 1) return;
		int const prev_n = power.size();
		power.resize(n + 1, 1);
		for (int i = std::max(1, prev_n); i <= n; ++i)
			power[i] = mul(power[i - 1], base);
	}

	static std::uint64_t add(std::uint64_t a, std::uint64_t b) {
		a += b;
		if (a >= MOD) a -= MOD;
		return a;
	}

	static std::uint64_t mul(std::uint64_t a, std::uint64_t b) {
		std::uint64_t au = a >> 31;
		std::uint64_t al = a & ((1ULL << 31) - 1);
		std::uint64_t bu = b >> 31;
		std::uint64_t bl = b & ((1ULL << 31) - 1);
		std::uint64_t ul = al * bu + au * bl;

		std::uint64_t res = au * bu * 2;
		res += ul >> 30;
		res += (ul & ((1ULL << 30) - 1)) << 31;
		res += al * bl;
		return add(res >> 61, res & MOD);
	}

	std::vector<std::uint64_t> hash;

public:
	RollingHash() = default;

	void build(std::string const &s) {
		int n = s.size();
		extend_power(n);
		hash.assign(n + 1, 0);
		for (int i = 0; i < n; ++i) hash[i + 1] = add(mul(hash[i], base), s[i]);
	}

	std::uint64_t find(int l, int r) {
		return add(hash[r], MOD - mul(hash[l], power[r - l]));
	}
};


#line 4 "test/string/rolling_hash/aoj_alds1_14_b.test.cpp"

#include <iostream>
#line 7 "test/string/rolling_hash/aoj_alds1_14_b.test.cpp"

using namespace std;

int main() {
	string t, p;
	cin >> t >> p;
	int n = p.size();

	RollingHash rht, rhp;
	rht.build(t);
	rhp.build(p);
	for (int i = 0; i <= (int)t.size() - n; ++i)
		if (rht.find(i, i + n) == rhp.find(0, n)) cout << i << endl;

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	141 ms	18 MB
g++	01_small_00.in	AC	12 ms	18 MB
g++	01_small_01.in	AC	12 ms	18 MB
g++	01_small_02.in	AC	12 ms	18 MB
g++	01_small_03.in	AC	12 ms	18 MB
g++	02_rand_00.in	AC	11 ms	18 MB
g++	02_rand_01.in	AC	12 ms	18 MB
g++	02_rand_02.in	AC	13 ms	18 MB
g++	02_rand_03.in	AC	12 ms	18 MB
g++	02_rand_04.in	AC	12 ms	18 MB
g++	02_rand_05.in	AC	13 ms	19 MB
g++	02_rand_06.in	AC	13 ms	19 MB
g++	02_rand_07.in	AC	18 ms	21 MB
g++	03_large_00.in	AC	13 ms	19 MB
g++	03_large_01.in	AC	13 ms	19 MB
g++	03_large_02.in	AC	18 ms	21 MB
g++	03_large_03.in	AC	20 ms	21 MB
g++	03_large_04.in	AC	60 ms	40 MB
g++	03_large_05.in	AC	61 ms	40 MB
g++	03_large_06.in	AC	60 ms	40 MB
g++	03_large_07.in	AC	60 ms	40 MB
g++	03_large_08.in	AC	60 ms	40 MB
g++	03_large_09.in	AC	59 ms	40 MB
g++	04_embedded_00.in	AC	61 ms	40 MB
g++	04_embedded_01.in	AC	62 ms	40 MB
g++	04_embedded_02.in	AC	60 ms	40 MB
g++	04_embedded_03.in	AC	61 ms	40 MB
g++	04_embedded_04.in	AC	61 ms	40 MB
g++	04_embedded_05.in	AC	60 ms	40 MB
g++	05_corner_00.in	AC	12 ms	18 MB
g++	05_corner_01.in	AC	11 ms	18 MB
g++	05_corner_02.in	AC	11 ms	18 MB
g++	05_corner_03.in	AC	944 ms	40 MB
g++	05_corner_04.in	AC	884 ms	40 MB
g++	05_corner_05.in	AC	60 ms	40 MB
g++	05_corner_06.in	AC	61 ms	40 MB
clang++	00_sample_00.in	AC	11 ms	20 MB
clang++	01_small_00.in	AC	12 ms	18 MB
clang++	01_small_01.in	AC	11 ms	18 MB
clang++	01_small_02.in	AC	11 ms	16 MB
clang++	01_small_03.in	AC	12 ms	18 MB
clang++	02_rand_00.in	AC	12 ms	20 MB
clang++	02_rand_01.in	AC	12 ms	20 MB
clang++	02_rand_02.in	AC	13 ms	18 MB
clang++	02_rand_03.in	AC	13 ms	16 MB
clang++	02_rand_04.in	AC	13 ms	18 MB
clang++	02_rand_05.in	AC	15 ms	19 MB
clang++	02_rand_06.in	AC	14 ms	19 MB
clang++	02_rand_07.in	AC	19 ms	23 MB
clang++	03_large_00.in	AC	14 ms	19 MB
clang++	03_large_01.in	AC	13 ms	19 MB
clang++	03_large_02.in	AC	19 ms	21 MB
clang++	03_large_03.in	AC	18 ms	21 MB
clang++	03_large_04.in	AC	61 ms	40 MB
clang++	03_large_05.in	AC	64 ms	38 MB
clang++	03_large_06.in	AC	60 ms	40 MB
clang++	03_large_07.in	AC	63 ms	40 MB
clang++	03_large_08.in	AC	64 ms	38 MB
clang++	03_large_09.in	AC	63 ms	38 MB
clang++	04_embedded_00.in	AC	64 ms	42 MB
clang++	04_embedded_01.in	AC	64 ms	40 MB
clang++	04_embedded_02.in	AC	63 ms	42 MB
clang++	04_embedded_03.in	AC	64 ms	40 MB
clang++	04_embedded_04.in	AC	63 ms	38 MB
clang++	04_embedded_05.in	AC	64 ms	42 MB
clang++	05_corner_00.in	AC	11 ms	16 MB
clang++	05_corner_01.in	AC	11 ms	18 MB
clang++	05_corner_02.in	AC	11 ms	16 MB
clang++	05_corner_03.in	AC	843 ms	40 MB
clang++	05_corner_04.in	AC	852 ms	40 MB
clang++	05_corner_05.in	AC	64 ms	42 MB
clang++	05_corner_06.in	AC	67 ms	42 MB

Back to top page