dsalgo/
xor_prefix_set_hash.rs

1use std::collections::{
2    HashMap,
3    HashSet,
4};
5
6use crate::rng_static_xorshift64::*;
7
8/// pseudo random hash function: xorshift64
9/// prefix set hashing method: cumulative xor
10
11pub struct PrefixSetHash<T>(HashMap<T, u64>);
12
13impl<T: Clone + std::hash::Hash + Eq> PrefixSetHash<T> {
14    pub fn new() -> Self {
15        Self(HashMap::new())
16    }
17
18    pub fn calc(
19        &mut self,
20        a: &[T],
21    ) -> Vec<u64> {
22        let mut s = HashSet::new();
23
24        let mut b: Vec<_> = a
25            .iter()
26            .map(|x| {
27                let v = self
28                    .0
29                    .entry(x.clone())
30                    .or_insert_with(|| static_xorshift64());
31
32                if s.contains(x) {
33                    0
34                } else {
35                    s.insert(x.clone());
36
37                    *v
38                }
39            })
40            .collect();
41
42        for i in 0..a.len() - 1 {
43            b[i + 1] ^= b[i];
44        }
45
46        b
47    }
48}
49
50#[cfg(test)]
51
52mod tests {
53
54    use super::*;
55
56    #[test]
57
58    fn test() {
59        // https://atcoder.jp/contests/abc250/tasks/abc250_e
60        let a = vec![1, 2, 3, 4, 5];
61
62        let b = vec![1, 2, 2, 4, 3];
63
64        let q = vec![
65            ((1, 1), true),
66            ((2, 2), true),
67            ((2, 3), true),
68            ((3, 3), false),
69            ((4, 4), false),
70            ((4, 5), true),
71            ((5, 5), false),
72        ];
73
74        let mut hash = PrefixSetHash::new();
75
76        let a = hash.calc(&a);
77
78        let b = hash.calc(&b);
79
80        for ((i, j), ans) in q {
81            let i = i - 1;
82
83            let j = j - 1;
84
85            assert_eq!(a[i] == b[j], ans);
86        }
87    }
88}
dsalgo/xor_prefix_set_hash.rs

dsalgo/
xor_prefix_set_hash.rs
