首先\(conn(conn(s_2,n_2),m) = conn(s_2,n_2 \times m)\)，因此我们可以找一个最大的\(m'\)满足\(conn(s_2, m')\)能由\(conn(s_1, n1)\)生成，然后再通过\(m = \lfloor \frac{m'}{n_2} \rfloor\)得到答案\(m\)
我们可以知道\(m' \leq \frac{|s_1| \times n_1}{|s_2|}\)。为了提高效率，我们考虑二进制拆分\(m' = \sum_{i=1}^{t}{2^{p_t}}\)，即把\(conn(s_2, m')\)看作\(conn(s_2,2^{p_t}),conn(s_2,2^{p_{t-1}}),...,conn(s_2,2^{p_1})\)个字符串一词拼接
我们考虑倍增，设\(jp_{i,j}\)表示从\(s_1\)的\(i\)位置开始，组成\(conn(s_2,2^j)\)要跳至少多少步，可以实现
最终复杂度\(O(|s|^2 \log{|s|n})\)