关于子串hash
  • 板块学术版
  • 楼主StillEmpty
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/8/24 12:43
  • 上次更新2023/10/27 13:53:53
查看原帖
关于子串hash
150956
StillEmpty楼主2022/8/24 12:43

我想实现一个字符串的子串间可以互相比较的hash。我唯一能想到的做法就是用常见的hash再乘底数的逆元。例如：

hk=∑i=1k131i×Simod  109+7h_k = \sum^{k}_{i=1}131^i \times S_i \mod 10^9+7

一个子串 S[l,r]S[l,r] 的hash就是：

(hr−hl−1)×(131109+5)lmod  109+7(h_r-h_{l-1}) \times (131^{10^9+5})^{l} \mod 10^9+7

请问这个做法合理吗，以及有更好的做法吗

2022/8/24 12:43