competitive_library/string/
rolling_hash.rs1use crate::other::xorshift::XorShift;
3
4const MOD: u128 = (1 << 61) - 1;
5
6pub fn rolling_hash<T: Into<u128> + Copy>(pattern: &[T], text: &[T]) -> Vec<usize> {
8 let rh = RollingHash::new(text, pattern.len());
9 rh.search(pattern)
10}
11
12pub struct RollingHash {
13 pub text_hash: Vec<u128>,
14 base: u128,
15 length: usize,
16}
17impl RollingHash {
18 pub fn new<T: Into<u128> + Copy>(text: &[T], length: usize) -> Self {
19 let base = XorShift::new()
20 .map(|x: u64| x as u128 % MOD)
21 .next()
22 .unwrap();
23 RollingHash::from_base(text, length, base)
24 }
25 pub fn from_base<T: Into<u128> + Copy>(text: &[T], length: usize, base: u128) -> Self {
26 let pow_base = pow_mod(base, length);
27
28 let mut hash = 0;
29
30 for &t in text.iter().take(length) {
31 hash = mul_mod(hash, base);
32
33 hash += t.into();
34 }
35 let mut text_hash = vec![hash];
36
37 for k in 0..text.len() - length {
38 hash = mul_mod(hash, base);
39 hash += text[length + k].into();
40
41 let buff = mul_mod(text[k].into(), pow_base);
42 if buff < hash {
43 hash -= buff;
44 } else {
45 hash += MOD - buff;
46 }
47
48 text_hash.push(hash);
49 }
50 Self {
51 text_hash,
52 base,
53 length,
54 }
55 }
56 pub fn search<T: Into<u128> + Copy>(&self, pattern: &[T]) -> Vec<usize> {
57 assert_eq!(self.length, pattern.len());
58
59 let mut pattern_hash = 0;
60
61 for &p in pattern {
62 pattern_hash = mul_mod(pattern_hash, self.base);
63 pattern_hash += p.into();
64 }
65
66 self.text_hash
67 .iter()
68 .enumerate()
69 .filter_map(|(i, &h)| if pattern_hash == h { Some(i) } else { None })
70 .collect()
71 }
72}
73
74fn mul_mod(a: u128, b: u128) -> u128 {
75 let mut t = a * b;
76 t = (t >> 61) + (t & MOD);
77
78 if t >= MOD { t - MOD } else { t }
79}
80fn pow_mod(base: u128, exp: usize) -> u128 {
81 let (mut a, mut exp) = (base, exp as u128);
82
83 if exp == 0 {
84 return 1;
85 }
86
87 let mut res = 1;
88 a %= MOD;
89
90 loop {
91 if exp % 2 == 1 {
92 res = mul_mod(res, a);
93 }
94
95 if exp == 1 {
96 return res;
97 }
98
99 exp /= 2;
100 a = mul_mod(a, a);
101 }
102}
103
104#[cfg(test)]
105mod tests {
106 use super::*;
107
108 #[test]
109 fn test_rolling_hash() {
110 let mut mached = false;
111 let s = b"hhggggghhhhhgghhhhhghgggggghggggghgghhggghhggghhhhhgggghhggggghhghghghhhhhhhgggghhhgghgggghhhggghhhgghhghhhghhghhhhhghghhghghggghhhhhghhgghghghhhhhghhhhgghhhhhghghgggggghhgghgghhghhgghghghghhghhhhhggggghggggghggggghhhhgggggghghgghhhhhhggghhhggghhghghhghhhhhhghghghhhghhhhgghhghghghgggghhghhhhgghhghghgghggghgghggggghggghhggghggghghhhgghhgggghhghhhhhghgghhhhghghhggghggghggghhhghhhgggghhhhghggghggghhggggghhghhhhhhhhggghgghhghhhhhgghhhhghhgghgghghgghghgghhgghggghghgghgghghggghghhghghhhhghhhhgghhghghhhhhghghhghghghgghhhghgghhhhhgggghhhhghghghgghhhghhhhhhhhhhhhghghghgghhhggghhhgghhhgghgghghggghhhgghhgggghhggghhghhghhhhghgghhgggghhghghhgghggggghgggghhghghhgghggggggggghhggghhhhghhhhghhggggggghhhhghhgghhhggghhghhghgghhhgghhhghgghhhhhhgghhhhgggghgghhhhhghghhhhgghhggghggghhgggghghhgghghhhgghhhhghghghggghhgggghhhhgghghhhhhhhhgghhhhgggghhgghhhghggghhghghggghhhghghhghgghggghhghhghgghghghhhgggggghghggghhhhgghhhhghghhgggghghhghgghghhhgghghhhhhghghghhgghhhhghhhgghghggggghghhhgghhhhghghhgghhghhhgghgghhhghghhgghggghhghghhgghgggghghhhhghhggghhhhhhggghgghhhghggggghhgggghhghhgghhgghhhhhghhhhhhgghhghhhhhghghghghghhggggggghghgghggghhhhhgghghhhghgghgghhhghghhhhggggghhghghghhgghghgghhgggggggghhhhhghghhhghghhhhhgghhgghhghgghghggghhgghghghhghghhghhhhghhhgggghghhghhhghhhhghhgghggghghghhghghhhggghhhgggghhggghhghgggghhhghghhhghhhhhhhghhgggghhhhgghggghhgghhhhgggghgggghhhhghhhggghhhgggggghggghgghghhhghggghghgghgggghhghhhghhgghghhhhghhgghhgghhhhhggghggghhghhghhgggghghgggghgghggghhhhhhghhghgghghhhhhghghhhggghgghghghgggghghhgghhhgghhgggggghggghhggghhhghhghghggghhggghghhhhhgghhgghhhhggghhhhgggghhhgghhggghghhghghghghhgghghggghgghgghghhgghhhghgghghhggghghhghhhhgghhghghhhghghhghghghhgghhhgghghhghggggghhhhhggggggggghhhhgghhhgghhghghggghghghhgggghghghhhgghgghhghhgghggggggghggghggghghgggghghhggghgghhhhhhgghhghggghgghhhhghhghghhhggggghhghhgghhgghhgghggghggghhhhhgghgggggghghhhhhghhhghhhghghghhhhhghggghhgghhhhhgggghhghhhhhghhgghhhgghgggghghgghggghhhhhhhhggghghghhhghhghhgghhghghhhgghghgghhhhggghhhggghhgghghgghhhhhggghhghghghghhgghghghhghghghhgggggghghhhghhhhhggghgghghhgghghhhhghhhhgghhghghhggggghghghghghhghgghggghhghhggghggghhggghhgghghhghggghgggghgghhhghgghgghhhghghghhghhhggghhhhgghhhhgghhhghghhghggggggghhhhghghhhgghhggghhghgghgghhhghhhghggghhggghghhgghhhghgghhhghhgghghhhghgghggghgghhghhggghhghhhhghgghgghggggghgghhhhhhghhgggggggghggggghgggggggghghhhhghhghggghgggghghghhghgghhgghhgghghhhghhghhghhgghgghhhgghghhhhgghghgghhgggghggggggghghghhghgggghghhgggghgghghhhhhgghhghgghghhggghghhghhghgghhggghhhhgghhhhhgggggghhggghhghhggghgghhghhhghhhhhgghhghgggggghgghggghhghgghghhgggggghgghhhghhhhghgghhhhhhghghhgghgghhgghhgghhhhhggggghhghhgghhghgghghghhhghgghggghghghgggghgghhggghghgghghhhhhhgggggghghghhhghhghhhgghghghgghhhghhggghggggggggghhhgghghhhhhhghgghgghgghghgghhhhhhgggghghhhhgggghgggggghhhghghghgghhghghhhhghgghhhhhgggggggggghghghggggggghgghhgghghhghhhhggghhghgggghghhghgghgghggghhhgghhhghgghhhhhghggghhhhghhghhhhghhggggghhhhhhhhghhhghghhggghhhhgggggghghhhgggghghhhgghhggghhghhghhgghggggggghhhgghgghghhhghgghhhghhhhhgghgghhhhgghhhhhhghhggghhhgghggggghghghghgghghgghhhhhhhhhhgghhhgghgghghhghhghgghgghggghghggghhhgghgghhhghghgghghghhhgghhggghhggggggghgghghhghghghhhhghhgghhhgghghhhghhghhhhhghhhgghgghhhghhhhghhhghghgghhghhgggggghgghghghhhghgghhhhhhhhhghghhhhhggggghgggghhhghgghhhghhhghhgghghhghggghggghhghgghhhghghhhhhggghhhghghhhgghhhhgghgggghhhghgghhggghhhggggghghhhgggghghgghhggghgg";
112
113 for i in 0..s.len() {
114 if i + 21 * 2 > s.len() {
115 break;
116 }
117 if !rolling_hash(&s[i..i + 21], s).is_empty() {
118 mached = true;
119 break;
120 }
121 }
122 assert!(mached);
123 }
124
125 #[test]
126 fn abc() {
127 let s = b"abcdefghijklmnopqrstuvwxyz";
128 assert_eq!(rolling_hash(s, s), vec![0]);
129
130 for i in 1..26 {
131 for j in 0..26 - i {
132 assert_eq!(rolling_hash(&s[j..j + i], s), vec![j], "{} {}", i, j);
133 }
134 }
135 }
136
137 #[test]
138 fn test_mul_mod() {
139 for i in XorShift::new().take(1000).map(|x: u64| x as u128 % MOD) {
140 for j in XorShift::new().take(1000).map(|x: u64| x as u128 % MOD) {
141 assert_eq!(mul_mod(i, j), (i * j) % MOD);
142 }
143 }
144 }
145 #[test]
146 fn test_pow_mod() {
147 use crate::math::mod_pow::modpow;
148 for i in XorShift::new().take(1000).map(|x: u64| x as u128 % MOD) {
149 for j in XorShift::new().take(1000).map(|x: u64| x as u128 % MOD) {
150 assert_eq!(
151 pow_mod(i, j as usize),
152 modpow(i as i64, j as i64, MOD as i64) as u128
153 );
154 }
155 }
156 }
157}
158
159#[cfg(test)]
160mod monoid {
161
162 use super::*;
163 use crate::structure::segment_tree::Monoid;
164 struct RollingHashMonoid {}
165 impl Monoid for RollingHashMonoid {
166 type T = (u128, u128);
167
168 fn identity_element() -> Self::T {
169 (0, 1)
170 }
171
172 fn binary_operation(a: &Self::T, b: &Self::T) -> Self::T {
173 (
174 {
175 let buff = mul_mod(a.0, b.1) + b.0;
176 if buff >= MOD { buff - MOD } else { buff }
177 },
178 mul_mod(a.1, b.1),
179 )
180 }
181 }
182
183 #[cfg(test)]
184 mod tests {
185 use crate::structure::segment_tree::SegmentTree;
186
187 use super::*;
188 #[test]
189 fn m() {
190 let mut sg = SegmentTree::<RollingHashMonoid>::new(29);
191 let base = XorShift::new()
192 .map(|x: u64| x as u128 % MOD)
193 .next()
194 .unwrap();
195
196 for (i, &value) in b"abcdefghijklmnopqrstuvwxyzabc".iter().enumerate() {
197 sg.set(i, (value as u128, base));
198 }
199
200 assert_eq!(sg.query(0, 3), sg.query(26, 29));
201 sg.set(3, (b'a' as u128, base));
202 sg.set(4, (b'b' as u128, base));
203 sg.set(5, (b'c' as u128, base));
204 assert_eq!(sg.query(0, 3), sg.query(3, 6));
205
206 let rh = RollingHash::new(b"abcdefghijklmnopqrstuvwxyzabc", 3);
207 assert_eq!(sg.query(0, 3).0, rh.text_hash[0]);
208 }
209 }
210}