Hacks

Worst-case generation for specific problems. More...

Functions
std::string	tgen::hack::abacaba (int n)
	Returns the prefix of the infinite word "abacabad...".
std::pair< std::string, std::string >	tgen::hack::unsigned_polynomial_hash_hack ()
	Returns two strings that force polynomial hash collision for power-of-two mod.
std::pair< std::string, std::string >	tgen::hack::polynomial_hash_hack (int alphabet_size, int base, int mod)
	Returns two strings that force polynomial hash collision given base and mod.
std::pair< std::string, std::string >	tgen::hack::polynomial_hash_hack (int alphabet_size, std::vector< int > bases, std::vector< int > mods)
	Returns two strings that force polynomial hash collision given bases and mods.
std::vector< long long >	tgen::hack::std_unordered (int size)
	List of integers that tries to force collision on std::unordered_set.
std::vector< std::pair< int, int > >	tgen::hack::mo (int n, int q)
	Query list that tries to force asymptotic worst-case for Mo's algorithm.
std::vector< std::string >	tgen::hack::string_set (int size)
	List of strings that have high cost to insert in a std::set.

Detailed Description

Worst-case generation for specific problems.

Examples

// Creates values that force collision on std::unordered_set.
std::vector<long long> unord_hack = tgen::hack::std_unordered(1e6);
 
// Creates queries that force worst-case for Mo's algorithm.
std::vector<std::pair<int, int>> mo_hack = tgen::hack::mo(1e6, 1e6);

Function Documentation

abacaba()

std::string tgen::hack::abacaba ( int n )

inline

Returns the prefix of the infinite word "abacabad...".

Parameters

n	Length of the prefix.

Returns

A string with the prefix of length n of "abacabad...".

Complexity

O(n).

Examples

// Prints "abacaba".
std::cout << tgen::hack::abacaba(7) << std::endl;

Definition at line 3827 of file tgen.h.

mo()

std::vector< std::pair< int, int > > tgen::hack::mo ( int n, int q )

inline

Query list that tries to force asymptotic worst-case for Mo's algorithm.

Parameters

n	Size of the array operated upon.
q	Number of queries to be returned.

The expected number of pointer moves are as follows, assuming standard implementations:

• For block-based Mo, assuming blocks of size b and q >> n / b: Theta(n^2 / b + q b).
• For Hilbert-based Mo: Theta(q sqrt(n)).

Complexity

O(n log n).

Examples

// Creates queries that force worst-case for Mo.
std::vector<std::pair<int, int>> hack = tgen::hack::mo(1e6, 1e6);

Definition at line 3921 of file tgen.h.

polynomial_hash_hack() [1/2]

std::pair< std::string, std::string > tgen::hack::polynomial_hash_hack ( int alphabet_size, int base, int mod )

inline

Returns two strings that force polynomial hash collision given base and mod.

Parameters

alphabet_size	Alphabet size.
base	Base.
mod	Mod.

Precondition

0 < base < mod

Computes two strings that have the same polynomial hash for given base and mod.
Characters are in [a, a + alphabet_size). The larger the alphabet, the smaller the colided strings.

Returns

A std::pair with the colided strings.

Reference:

• On the mathematics behind rolling hashes and anti-hash tests: Composition-attack: Multiple hashes

Complexity

O(sqrt(mod) log mod).

Examples

// Prints polynomial hash hack.
std::cout << tgen::print(tgen::hack::polynomial_hash_hack(2, 31, 1e9+7), '\n') << std::endl;

Definition at line 3858 of file tgen.h.

polynomial_hash_hack() [2/2]

std::pair< std::string, std::string > tgen::hack::polynomial_hash_hack ( int alphabet_size, std::vector< int > bases, std::vector< int > mods )

inline

Returns two strings that force polynomial hash collision given bases and mods.

Parameters

alphabet_size	Alphabet size.
bases	Bases.
mods	Mods.

Precondition

|bases| = |mods| <= 2.
0 < bases[i] < mods[i].

Computes two strings that have the same polynomial hash for given bases and mods, up to 2 (base, mod) pairs.
Characters are in [a, a + alphabet_size). The larger the alphabet, the smaller the colided strings.

Returns

A std::pair with the colided strings.

Reference:

• On the mathematics behind rolling hashes and anti-hash tests: Composition-attack: Multiple hashes

Complexity

O(sqrt(mod) log^2 mod), with mod = max(mods).

Examples

// Prints polynomial hash hack for double hash.
std::cout << tgen::print(tgen::hack::polynomial_hash_hack(2, {31, 33}, {1000000007, 1000000009}), '\n') << std::endl;

Definition at line 3874 of file tgen.h.

std_unordered()

std::vector< long long > tgen::hack::std_unordered ( int size )

inline

List of integers that tries to force collision on std::unordered_set.

Parameters

size	Size of the list.

Creates hack for both std::unordered_set and std::unordered_map, forcing quadratic behavior. The hack might not be effective due to differences in C++ implementations.

Note

The hack might not be effective due to differences in C++ implementations.
This function benefits from tgen::set_compiler and tgen::set_cpp_version information.

Complexity

O(size).

Examples

// Creates values that force collision.
std::vector<long long> hack = tgen::hack::std_unordered(1e6);

Definition at line 3894 of file tgen.h.

string_set()

std::vector< std::string > tgen::hack::string_set ( int size )

inline

List of strings that have high cost to insert in a std::set.

Parameters

size	Size of the list.

Inserting these strings in a std::set takes Theta(size log(size)) time, and that is asymptotically the maximum one can achieve.

Complexity

O(size log(size)).

Examples

// Creates strings that have high cost to insert in std::set.
std::vector<std::string> hack = tgen::hack::string_set(1e6);

Definition at line 3934 of file tgen.h.

unsigned_polynomial_hash_hack()

std::pair< std::string, std::string > tgen::hack::unsigned_polynomial_hash_hack ( )

inline

Returns two strings that force polynomial hash collision for power-of-two mod.

Computes two strings that have the same polynomial hash for any base and power-of-two mod (up to 2^64).
Characters are in [a, b].

Returns

A std::pair with the colided strings.

Reference:

• On the mathematics behind rolling hashes and anti-hash tests: Thue–Morse sequence: Hashing with unsigned overflow (p = 2^64, q arbitrary).

Complexity

O(1).

Examples

// Prints unsined polynomial hash hack.
std::cout << tgen::print(tgen::hack::unsigned_polynomial_hash_hack()) << std::endl;

Definition at line 3844 of file tgen.h.