滚动HASH

12个月前 阅读 197 评论 0 赞 0
  1. ULL base = 2333;
  2. ULL p[2 * MAX_N];//v[x]=V^x%Z
  3. ULL Hash[2 * MAX_N];//u[x]=hashvalue(1,x);
  4. void init(char *s, int k) //预处理主串的Hash前缀hash值和p的次方.
  5. {
  6. p[0] = 1;
  7. Hash[0] = 0;
  8. for (int i = 1; i <= k; i++) p[i] = p[i - 1] * base;
  9. for (int i = 1; i <= k; i++) {
  10. Hash[i] = Hash[i - 1] * base + (s[i] - 'a' + 1);
  11. }
  12. }
  13. ULL get(int l, int r) //由公式得到hash[r-l]的值,下标从1开始
  14. {
  15. return Hash[r] - Hash[l - 1] * p[r - l + 1];
  16. }
你的支持将鼓励作者继续创作

评论(0)

(无)