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:
