代数学不存在了！多项式也能哈希？

· · 算法·理论

前言

我又来口胡新算法啦！这次写文章的时间比较仓促，可能漏洞百出，欢迎各位指正。orz

懒得 p 牢九门了，将就着看

小引子

大家学字符串算法时，有没有这样一种感受：算法难度两极分化。字符串哈希、字典树偏简单，其他算法又偏难。这启发了我：多项式算法都难度很大，难道没有难度小的算法吗？

有的兄弟，有的。这样简单又的强势的算法就是我今天分享的多项式哈希。

算法简述

回想字符串哈希，我们是如何把计算机不便于处理的字符串转化为一个便于计算机处理的东西的？一般我们都会把字符串通过各种哈希手段变成一个数字，来方便计算机实现判等等操作。

多项式哈希也一样，甚至更简单：假设我们有一个 n 项多项式 f(x)=\sum\limits^{n-1}_{0}a_ix^i=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\dots+a_1x+a_0，我们如何把它变成一个数字呢？没错，就是带入一个具体的 x。

那么问题就来了，该带入谁呢？我们结合进制的思想思考一下：把代入的数看作一个 x 进制的数