提高篇-字符串专题-《算法笔记》同步笔记总结与补充

本章内容有点极端，字符串hash难度一般，理解起来问题不大，即利用素数和大数做hash散列避免冲突，之前八数码问题也使用过康拓展开式标识唯一的字符串；KMP学过三遍了，理解起来还是废了番功夫，重点仍然是next[]数组的含义和求解，除此之外增加了统计子串出现的次数，优化next[]数组，有限状态机解释KMP算法（对理解很有帮助）

专题要点：

• 字符串hash：hash[i] = (hash[i - 1] * p + index(str[i])) % mod

  • 从进制转换的角度理解，hash是p进制转换为十进制的数字，把hash[i - 1]当做p进制，并将其转换为十进制，加上str[i]的int类型，对mod取余

  • hash[]的理解：hash[i]表示从str[0~i]子串的hash值，hash[length - 1]（length是字符串的长度）表示整个字符串的hash值

  • 几个数据结构：

    • powP[]:存放p^i^%mod的计算结果，便于求子串hash值直接访问，其中powP[0] = 1

    • hash[]:表示从str[0~i]子串的hash值

    • vector<pair<int, int> >sub:存放所有<子串hash值，子串长度>

• KMP算法：得next数组得天下，新收获的内容开头以及提及了，确实不易理解就不再赘述了

打赏

Thanks

支付宝

微信