Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Sugar_fan's blog

By Sugar_fan, 8 months ago, In English

Hello, Codeforces!

For the convenience of hacking codes that incorrectly use rolling hashes (i.e., using fixed modulos and bases), I wrote a tool in Rust, which runs entirely on the frontend and requires WebAssembly support.

Try it here and feel free to create issues.

Explanation of parameters:

  • length: the length of generated strings;
  • λ (lambda):detail follows;
  • δ (delta) and η (eta) : parameters of L2 algorithm;
  • precision: floating-point precision in decimal.

Given the modulos {pi}n1i=0 and the bases {qi}n1i=0, define hi(a)=(length1j=0qjisj)mod, where a is a string of \text{length}. We want to find two strings a and b of \text{length} such that h_i(a)=h_i(b) for every i.

If we find a integer array d of \text{length} satisfying that h_i(d)=0 for every i, |d_j|<26 for every j, and d_j\ne 0 for some j, we can easily construct a and b from d.

Construct a matrix M of size (n+\text{length})\times(n+\text{length}):

M=\begin{bmatrix} Q & I\\ P & 0 \end{bmatrix}.

where

  • Q is a matrix of size \text{length} \times n , where Q_{ji}=q_i^j\bmod p_i;
  • I is an identity matrix of size (\text{length} \times \text{length});
  • P is a diagonal matrix of size n\times n, where P_{ii}=p_i,
  • 0 is a zero matrix of size n\times \text{length}.

We can find that the matrix M has the following properties:

  • For every row R of M, that h_i(R[n\cdots n+\text{length}])\equiv R[i] \pmod{p_i} holds for every i,
  • M is full rank.

Define the following operation:

  • R_i\leftarrow R_i-R_j\times k, where k\in \mathbb Z.

We can find that this operation does not affect the properties of the matrix.

If after operations, there exists a row R satisfying that R[i]=0 for every i<n and |R[i]|<26 for every i\ge n, we can find a solution d=R[n\cdots n+\text{length}].

Intuitively, we should find the "shortest" row R^*. To make it more likey that R^*[i]=0 for every i<n, multiply the first n columns by a big integer \lambda, i.e.,

M=\begin{bmatrix} \lambda Q & I\\ \lambda P & 0 \end{bmatrix}.

This is well known as Shortest Vector Problem (SVP). Here, we use the L^2 algorithm to reduce M. More details about L^2 algorithm can be found in the paper mentioned below.

References:

  • Vote: I like it
  • +328
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Please delete this and never hack any hash solution again

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Please write suffix array template and never submit hashing solution again

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it cant solve all the problems solvable with hashes

»
8 months ago, # |
  Vote: I like it +180 Vote: I do not like it

New fear unlocked

»
8 months ago, # |
Rev. 2   Vote: I like it +43 Vote: I do not like it

Orz!

It seems that people use the rolling hash formula \sum_{j = 0}^{n - 1} q^{n - 1 - j} s_j more frequently than \sum_{j = 0}^{n - 1} q^{j} s_j. Probably it would be better to have an "reverse the result" option.

»
8 months ago, # |
  Vote: I like it +79 Vote: I do not like it

Please no GOD no please. I won't play Genshin any more. Please don't hack my Hash.

»
8 months ago, # |
  Vote: I like it +38 Vote: I do not like it

the hero we do not deserve

»
8 months ago, # |
  Vote: I like it +46 Vote: I do not like it