字符串的有关算法教程.ppt

字符串的相关算法;还是在前面的话;大前天提到了分治… 提到了这样一个方程… f(n)=f(n/2)+f(n/2)+O(1) 这个咱当时是说f(n)=O(nlogn) 那是咱SB… Too Na?ve 考虑线段树的节点，就是这个分布的… 可是线段树的节点个数是O(n)的 这个的解显然应该是f(n)=O(n) 在此表示歉意;咱所知道的字符串算法 Pascal的Pos函数… Hash哈希 Kmp和扩展Kmp Trie树 AC自动机 后缀树，后缀数组(SA)，后缀自动机(SAM) Manacher算法 乱搞 最近新出来的：回文自动机(PAM)(太弱不会)。 ;Hash哈希;实际上这种计算方法，每个字符串都是X进制下的一个数，而Hash值就是这个X进制的数转十进制的值，由于X进制的数互不相同，显然Hash值，即十进制的数也互不相同。 Q：那如果字符串长度过大，以致会爆怎么办？ 取个模呗… Q：那如果两个字符串不同Hash值取某个模最后相同怎么办？ 取多个模呗…如果多个模的情况下都相同那么就是同一个字符串。 Q：如果取多个模都相同呢？ …… 首先，这个模是你自己定的，所以一般数据是没办法全部卡的。接着，由中国剩余定理，只要取到的每个模足够大，那么最后也可以保证一定范围内的Hash值是一定的。 Q：中国剩余定理是什么？ 以后讲数学的时候会讲吧…顺便可以百度_(:зゝ∠)_;除了这种Hash以外，