Skip to content

Latest commit

 

History

History
42 lines (34 loc) · 2.64 KB

strings.md

File metadata and controls

42 lines (34 loc) · 2.64 KB

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 264. 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*109. Also, you cannot specify more than two pairs (mod, base).
  • Complexity and result size: for two mods around 2*109 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";