Strings

Strings are generated with the help of StringRandom class. As usual, you should interact with it via its global instance rnds.

Generators (rnds static methods)

std::string random(int len, const std::string& alphabet = "a-z")

• Returns: random string of length len made of characters from alphabet.
• Note: alphabet can contain single chars and groups of form A-Z. For example, "0-9abcdefA-F" includes all hexadecimal characters.

std::string random(const std::string& pattern, ...)

• Returns: a random string generated by pattern.
• Equivalent to rnd.next(pattern, ...); see docs on Random for detailed description.

std::string thueMorse(int len, char first = 'a', char second = 'b')

• Returns: a prefix of length n of the Thue-Morse string made of first and second characters.
• Description: Thue-Morse string is a string of kind 0110100110010110.... That is, start from 0 and on each step concatenate the string to itself exchanging zeroes and ones.
• Note: this string is useful for breaking hashes modulo 2⁶⁴. Strings thueMorse(n, x, y) and thueMorse(n, y, x) will have identical polynomial hash for any base for n ≥ 2048.

std::string abacaba(int len, char first = 'a')

• Returns: a prefix of length n of the string of form abacabadabacaba... starting with character first.

std::pair<std::string, std::string> antiHash(
  const std::vector<std::pair<long long, long long>>& bases,
  const std::string& alphabet = "a-z",
  int length = -1)

• Returns: a pair of different strings of length length (or minimal found if length is -1) with the same polynomial hash for specified bases.
• Parameters:
  • bases: vector of pairs (mod, base);
  • alphabet: the same as in random(len, alphabet);
  • length: length of resulting strings, or -1 if the shortest found result is needed.
• Note: mod must not exceed 2×10⁹. Also, you cannot specify more than two pairs (mod, base).
• Complexity and result size: for two mods around 2×10⁹ generation runs for about 3 seconds and produces strings of length approximately 100-200. A faster version of the algorithm will be presented later.
• Example:

int mod1 = rndm.randomPrime(1999000000, 2000000000);
int mod2 = rndm.randomPrime(1999000000, 2000000000);
int base1 = rnd.next(2000, 10000) * 2 + 1;
int base2 = rnd.next(2000, 10000) * 2 + 1;

auto res = rnds.antiHash( {{mod1, base1}, {mod2, base2}}, "a-z", -1);
cout << res.first << "\n" << res.second << "\n";

// or simply
cout << rnds.antiHash({{1000000007, 107}, {1000000009, 109}}) << "\n";