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$$$ (
`lambda`

)：detail follows; - $$$\delta$$$ (
`delta`

) and $$$\eta$$$ (`eta`

) : parameters of $$$L^2$$$ algorithm; `precision`

: floating-point precision in decimal.

Given the modulos $$$\lbrace p_i\rbrace_{i=0}^{n-1}$$$ and the bases $$$\lbrace q_i\rbrace_{i=0}^{n-1}$$$, define $$$h_i(a)=\Big(\sum\limits_{j=0}^{\text{length}-1} q_i^js_j\Big)\bmod p_i$$$, 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})$$$:

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.,

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:

Please delete this and never hack any hash solution again

Please write suffix array template and never submit hashing solution again

it cant solve all the problems solvable with hashes

New fear unlocked

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.

Well, it's added.

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

the hero we do not deserve