1# ref: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
2from titan_pylib.data_structures.splay_tree.reversible_lazy_splay_tree_array import (
3 ReversibleLazySplayTreeArrayData,
4 ReversibleLazySplayTreeArray,
5)
6from typing import Optional, Final
7import random
8import string
9
10_titan_pylib_DynamicHashString_MOD: Final[int] = (1 << 61) - 1
11_titan_pylib_DynamicHashString_DIC: Final[dict[str, int]] = {
12 c: i for i, c in enumerate(string.ascii_lowercase, 1)
13}
14_titan_pylib_DynamicHashString_MASK30: Final[int] = (1 << 30) - 1
15_titan_pylib_DynamicHashString_MASK31: Final[int] = (1 << 31) - 1
16_titan_pylib_DynamicHashString_MASK61: Final[int] = _titan_pylib_DynamicHashString_MOD
17
18
[docs]
19class DynamicHashStringBase:
20 """動的な文字列に対するロリハです。
21
22 平衡二分木にモノイドを載せてるだけです。こんなライブラリ必要ないです。
23
24 Example:
25 ```
26 base = DynamicHashStringBase(2 * 10**5 + 1)
27 dhs_s = DynamicHashString(base, s)
28 dhs_t = DynamicHashString(base, t)
29
30 pref = dhs_s.get(0, r)
31 suff = dhs_t.get(l, n)
32 h = base.unite(pref, suff, n-l)
33 ```
34 """
35
36 def __init__(self, n: int = 0, base: int = -1, seed: Optional[int] = None) -> None:
37 assert n >= 0
38 rand = random.Random(seed)
39 base = rand.randint(37, 10**9) if base < 0 else base
40 powb = [1] * (n + 1)
41 for i in range(1, n + 1):
42 powb[i] = self.get_mul(powb[i - 1], base)
43 op = lambda s, t: (self.unite(s[0], t[0], t[1]), s[1] + t[1])
44 e = (0, 0)
45 self.base = base
46 self.data = ReversibleLazySplayTreeArrayData(op=op, e=e)
47 self.n = n
48 self.powb = powb
49
[docs]
50 @staticmethod
51 def get_mul(a: int, b: int) -> int:
52 au = a >> 31
53 ad = a & _titan_pylib_DynamicHashString_MASK31
54 bu = b >> 31
55 bd = b & _titan_pylib_DynamicHashString_MASK31
56 mid = ad * bu + au * bd
57 midu = mid >> 30
58 midd = mid & _titan_pylib_DynamicHashString_MASK30
59 return DynamicHashStringBase.get_mod(
60 au * bu * 2 + midu + (midd << 31) + ad * bd
61 )
62
[docs]
63 @staticmethod
64 def get_mod(x: int) -> int:
65 # 商と余りを計算して足す->割る
66 xu = x >> 61
67 xd = x & _titan_pylib_DynamicHashString_MASK61
68 res = xu + xd
69 if res >= _titan_pylib_DynamicHashString_MOD:
70 res -= _titan_pylib_DynamicHashString_MOD
71 return res
72
[docs]
73 def extend(self, cap: int) -> None:
74 pre_cap = len(self.powb)
75 powb = self.powb
76 powb += [0] * cap
77 for i in range(pre_cap, pre_cap + cap):
78 powb[i] = DynamicHashStringBase.get_mul(powb[i - 1], self.base)
79
[docs]
80 def get_cap(self) -> int:
81 return len(self.powb)
82
[docs]
83 def unite(self, h1: int, h2: int, k: int) -> int:
84 """2つの hash 値を concat します。
85
86 Args:
87 h1 (int): prefix
88 h2 (int): suffix
89 k (int): h2の長さ
90
91 Returns:
92 int: h1 + h2
93 """
94 # h1, h2, k
95 # len(h2) == k
96 # h1 <- h2
97 if k >= self.get_cap():
98 self.extend(k - self.get_cap() + 1)
99 return self.get_mod(self.get_mul(h1, self.powb[k]) + h2)
100
101
[docs]
102class DynamicHashString:
103
104 def __init__(self, hsb: DynamicHashStringBase, s: str) -> None:
105 self.hsb = hsb
106 self.splay: ReversibleLazySplayTreeArray[tuple[int, int], None] = (
107 ReversibleLazySplayTreeArray(
108 hsb.data, ((_titan_pylib_DynamicHashString_DIC[c], 1) for c in s)
109 )
110 )
111
[docs]
112 def insert(self, k: int, c: str) -> None:
113 """位置 ``k`` に ``c`` を挿入します。
114 :math:`O(\\log{n})` です。
115 """
116 self.splay.insert(k, (_titan_pylib_DynamicHashString_DIC[c], 1))
117
[docs]
118 def pop(self, k: int) -> int:
119 return self.splay.pop(k)
120
[docs]
121 def reverse(self, l: int, r: int) -> None:
122 self.splay.reverse(l, r)
123
[docs]
124 def all_reverse(self) -> None:
125 self.splay.all_reverse()
126
[docs]
127 def split(self, k: int) -> tuple["DynamicHashString", "DynamicHashString"]:
128 left, right = self.splay.split(k)
129 return (DynamicHashString(self.hsb, left), DynamicHashString(self.hsb, right))
130
[docs]
131 def all_get(self) -> int:
132 return self.splay.all_prod()[0]
133
[docs]
134 def get(self, l: int, r: int) -> int:
135 return self.splay.prod(l, r)[0]
136
[docs]
137 def extend(self, other: "DynamicHashString") -> None:
138 assert self.hsb is other.hsb
139 self.splay.merge(other.splay)
140
141 def __getitem__(self, k: int) -> int:
142 return self.splay[k][0]
143
[docs]
144 def set(self, k: int, c: str) -> None:
145 self.splay[k] = (_titan_pylib_DynamicHashString_DIC[c], 1)
146
147 def __setitem__(self, k: int, c: str) -> None:
148 return self.set(k, c)
149
150 def __len__(self) -> int:
151 return len(self.splay)
152
153 def __str__(self) -> str:
154 return str([self[i] for i in range(len(self))])