算法理解
将一个字符串,转化成数字,这样可以省去一个一个字母比较的复杂度。
数位哈希
将一个字符串中的一个元素看成一位数,把整个字符串,看成是一个p进制数,由于可能这个字符串对应的数太大了,所以我们需要取模运算,但是有可能就会有两个不一样的字符串数值相等,就是哈希冲突
取模有两种方式,自然溢出,手输模数,自然溢出和常用模数容易被卡,所以我采用某人的生日作为模数(20081203)
T1:(卡了6个多小时,重构了3次)
非常讨厌的一道题,哈希+二分复杂度O(nlogn),枚举中间点或位置,依次向两边拓展,正反跑一遍哈希,用前缀和统计,考虑前缀和时加的哈希值并不是完全符合数位的,还需要自己推导数位,考虑进制的差。
注:要学会把程序拆分成各个函数,方便思考和调试,还有就是做前缀和时要注意下标不得从0开始,若是的话会出现UB,我的程序本地过不了,开了交上去开O2就过了