思路
刚开始我是写的暴力+倍增排序,全盘 WA 掉之后怀疑人生。然后看正解,二分果然很毒瘤。
先准备数据,写好字符串哈希。读者如果不清楚如何求字符串哈希的话就来看着篇文章:字符串哈希例题
我们先来简述一下字符串哈希。首先我们把字符串中的字符转换为数值,比如我们使用以下函数来搞定:
\[toNum(character) = character – numberOf(‘a’) + 1\]
然后,我们来定义一个值\(bitNum\)来作为进位值。所以,我们的前缀哈希函数有一个递推式如下:
\[Hash(i) = Hash(i-1)*bitNum + toNum(S[i])\]
我们可以来探寻这个前缀哈希函数的相减线性性。我们设\(|S|,|T|\)为这两个字符串的长度。我们得出:
\[Hash(|T|) = Hash(|S+T|) – Hash(|S|)*bitNum^{|T|}(1.1)\]