dynamic_hash_string¶
ソースコード¶
from titan_pylib.string.dynamic_hash_string import DynamicHashStringBase
from titan_pylib.string.dynamic_hash_string import DynamicHashString
展開済みコード¶
1# from titan_pylib.string.dynamic_hash_string import DynamicHashString
2# ref: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
3# from titan_pylib.data_structures.splay_tree.reversible_lazy_splay_tree_array import (
4# ReversibleLazySplayTreeArrayData,
5# ReversibleLazySplayTreeArray,
6# )
7from array import array
8from typing import (
9 Generic,
10 TypeVar,
11 Callable,
12 Iterable,
13 Optional,
14 Union,
15 Sequence,
16)
17
18T = TypeVar("T")
19F = TypeVar("F")
20
21
22class ReversibleLazySplayTreeArrayData(Generic[T, F]):
23
24 def __init__(
25 self,
26 op: Optional[Callable[[T, T], T]] = None,
27 mapping: Optional[Callable[[F, T], T]] = None,
28 composition: Optional[Callable[[F, F], F]] = None,
29 e: T = None,
30 id: F = None,
31 ) -> None:
32 self.op: Callable[[T, T], T] = (lambda s, t: e) if op is None else op
33 self.mapping: Callable[[F, T], T] = (lambda f, s: e) if op is None else mapping
34 self.composition: Callable[[F, F], F] = (
35 (lambda f, g: id) if op is None else composition
36 )
37 self.e: T = e
38 self.id: F = id
39 self.keydata: list[T] = [e, e, e]
40 self.lazy: list[F] = [id]
41 self.arr: array[int] = array("I", bytes(16))
42 # left: arr[node<<2]
43 # right: arr[node<<2|1]
44 # size: arr[node<<2|2]
45 # rev: arr[node<<2|3]
46 self.end: int = 1
47
48 def reserve(self, n: int) -> None:
49 if n <= 0:
50 return
51 self.keydata += [self.e] * (3 * n)
52 self.lazy += [self.id] * n
53 self.arr += array("I", bytes(16 * n))
54
55
56class ReversibleLazySplayTreeArray(Generic[T, F]):
57
58 def __init__(
59 self,
60 data: "ReversibleLazySplayTreeArrayData",
61 n_or_a: Union[int, Iterable[T]] = 0,
62 _root: int = 0,
63 ):
64 self.data = data
65 self.root = _root
66 if not n_or_a:
67 return
68 if isinstance(n_or_a, int):
69 a = [data.e for _ in range(n_or_a)]
70 elif not isinstance(n_or_a, Sequence):
71 a = list(n_or_a)
72 else:
73 a = n_or_a
74 if a:
75 self._build(a)
76
77 def _build(self, a: Sequence[T]) -> None:
78 def rec(l: int, r: int) -> int:
79 mid = (l + r) >> 1
80 if l != mid:
81 arr[mid << 2] = rec(l, mid)
82 if mid + 1 != r:
83 arr[mid << 2 | 1] = rec(mid + 1, r)
84 self._update(mid)
85 return mid
86
87 n = len(a)
88 keydata, arr = self.data.keydata, self.data.arr
89 end = self.data.end
90 self.data.reserve(n + end - len(keydata) // 3 + 1)
91 self.data.end += n
92 for i, e in enumerate(a):
93 keydata[(end + i) * 3 + 0] = e
94 keydata[(end + i) * 3 + 1] = e
95 keydata[(end + i) * 3 + 2] = e
96 self.root = rec(end, n + end)
97
98 def _make_node(self, key: T) -> int:
99 data = self.data
100 if data.end >= len(data.arr) // 4:
101 data.keydata.append(key)
102 data.keydata.append(key)
103 data.keydata.append(key)
104 data.lazy.append(data.id)
105 data.arr.append(0)
106 data.arr.append(0)
107 data.arr.append(1)
108 data.arr.append(0)
109 else:
110 data.keydata[data.end * 3 + 0] = key
111 data.keydata[data.end * 3 + 1] = key
112 data.keydata[data.end * 3 + 2] = key
113 data.end += 1
114 return data.end - 1
115
116 def _propagate(self, node: int) -> None:
117 data = self.data
118 arr = data.arr
119 if arr[node << 2 | 3]:
120 keydata = data.keydata
121 keydata[node * 3 + 1], keydata[node * 3 + 2] = (
122 keydata[node * 3 + 2],
123 keydata[node * 3 + 1],
124 )
125 arr[node << 2], arr[node << 2 | 1] = arr[node << 2 | 1], arr[node << 2]
126 arr[node << 2 | 3] = 0
127 arr[arr[node << 2] << 2 | 3] ^= 1
128 arr[arr[node << 2 | 1] << 2 | 3] ^= 1
129 nlazy = data.lazy[node]
130 if nlazy == data.id:
131 return
132 lnode, rnode = arr[node << 2], arr[node << 2 | 1]
133 keydata, lazy = data.keydata, data.lazy
134 lazy[node] = data.id
135 if lnode:
136 lazy[lnode] = data.composition(nlazy, lazy[lnode])
137 keydata[lnode * 3 + 0] = data.mapping(nlazy, keydata[lnode * 3 + 0])
138 keydata[lnode * 3 + 1] = data.mapping(nlazy, keydata[lnode * 3 + 1])
139 keydata[lnode * 3 + 2] = data.mapping(nlazy, keydata[lnode * 3 + 2])
140 if rnode:
141 lazy[rnode] = data.composition(nlazy, lazy[rnode])
142 keydata[rnode * 3 + 0] = data.mapping(nlazy, keydata[rnode * 3 + 0])
143 keydata[rnode * 3 + 1] = data.mapping(nlazy, keydata[rnode * 3 + 1])
144 keydata[rnode * 3 + 2] = data.mapping(nlazy, keydata[rnode * 3 + 2])
145
146 def _update_triple(self, x: int, y: int, z: int) -> None:
147 # data = self.data
148 # keydata, arr = data.keydata, data.arr
149 # lx, rx = arr[x<<2], arr[x<<2|1]
150 # ly, ry = arr[y<<2], arr[y<<2|1]
151 # self._propagate(lx)
152 # self._propagate(rx)
153 # self._propagate(ly)
154 # self._propagate(ry)
155 # arr[z<<2|2] = arr[x<<2|2]
156 # arr[x<<2|2] = 1 + arr[lx<<2|2] + arr[rx<<2|2]
157 # arr[y<<2|2] = 1 + arr[ly<<2|2] + arr[ry<<2|2]
158 # keydata[z*3+1] = keydata[x*3+1]
159 # keydata[z*3+2] = keydata[x*3+2]
160 # keydata[x*3+1] = data.op(data.op(keydata[lx*3+1], keydata[x*3]), keydata[rx*3+1])
161 # keydata[x*3+2] = data.op(data.op(keydata[rx*3+2], keydata[x*3]), keydata[lx*3+2])
162 # keydata[y*3+1] = data.op(data.op(keydata[ly*3+1], keydata[y*3]), keydata[ry*3+1])
163 # keydata[y*3+2] = data.op(data.op(keydata[ry*3+2], keydata[y*3]), keydata[ly*3+2])
164 self._update(x)
165 self._update(y)
166 self._update(z)
167
168 def _update_double(self, x: int, y: int) -> None:
169 # data = self.data
170 # keydata, arr = data.keydata, data.arr
171 # lx, rx = arr[x<<2], arr[x<<2|1]
172 # self._propagate(lx)
173 # self._propagate(rx)
174 # arr[y<<2|2] = arr[x<<2|2]
175 # arr[x<<2|2] = 1 + arr[lx<<2|2] + arr[rx<<2|2]
176 # keydata[y*3+1] = keydata[x*3+1]
177 # keydata[y*3+2] = keydata[x*3+2]
178 # keydata[x*3+1] = data.op(data.op(keydata[lx*3+1], keydata[x*3]), keydata[rx*3+1])
179 # keydata[x*3+2] = data.op(data.op(keydata[rx*3+2], keydata[x*3]), keydata[lx*3+2])
180 self._update(x)
181 self._update(y)
182
183 def _update(self, node: int) -> None:
184 data = self.data
185 keydata, arr = data.keydata, data.arr
186 lnode, rnode = arr[node << 2], arr[node << 2 | 1]
187 self._propagate(lnode)
188 self._propagate(rnode)
189 arr[node << 2 | 2] = 1 + arr[lnode << 2 | 2] + arr[rnode << 2 | 2]
190 keydata[node * 3 + 1] = data.op(
191 data.op(keydata[lnode * 3 + 1], keydata[node * 3 + 0]),
192 keydata[rnode * 3 + 1],
193 )
194 keydata[node * 3 + 2] = data.op(
195 data.op(keydata[rnode * 3 + 2], keydata[node * 3 + 0]),
196 keydata[lnode * 3 + 2],
197 )
198
199 def _splay(self, path: list[int], d: int) -> None:
200 arr = self.data.arr
201 g = d & 1
202 while len(path) > 1:
203 pnode = path.pop()
204 gnode = path.pop()
205 f = d >> 1 & 1
206 node = arr[pnode << 2 | g ^ 1]
207 nnode = (pnode if g == f else node) << 2 | f
208 arr[pnode << 2 | g ^ 1] = arr[node << 2 | g]
209 arr[node << 2 | g] = pnode
210 arr[gnode << 2 | f ^ 1] = arr[nnode]
211 arr[nnode] = gnode
212 self._update_triple(gnode, pnode, node)
213 if not path:
214 return
215 d >>= 2
216 g = d & 1
217 arr[path[-1] << 2 | g ^ 1] = node
218 pnode = path.pop()
219 node = arr[pnode << 2 | g ^ 1]
220 arr[pnode << 2 | g ^ 1] = arr[node << 2 | g]
221 arr[node << 2 | g] = pnode
222 self._update_double(pnode, node)
223
224 def _kth_elm_splay(self, node: int, k: int) -> int:
225 arr = self.data.arr
226 if k < 0:
227 k += arr[node << 2 | 2]
228 d = 0
229 path = []
230 while True:
231 self._propagate(node)
232 t = arr[arr[node << 2] << 2 | 2]
233 if t == k:
234 if path:
235 self._splay(path, d)
236 return node
237 d = d << 1 | (t > k)
238 path.append(node)
239 node = arr[node << 2 | (t < k)]
240 if t < k:
241 k -= t + 1
242
243 def _left_splay(self, node: int) -> int:
244 if not node:
245 return 0
246 self._propagate(node)
247 arr = self.data.arr
248 if not arr[node << 2]:
249 return node
250 path = []
251 while arr[node << 2]:
252 path.append(node)
253 node = arr[node << 2]
254 self._propagate(node)
255 self._splay(path, (1 << len(path)) - 1)
256 return node
257
258 def _right_splay(self, node: int) -> int:
259 if not node:
260 return 0
261 self._propagate(node)
262 arr = self.data.arr
263 if not arr[node << 2 | 1]:
264 return node
265 path = []
266 while arr[node << 2 | 1]:
267 path.append(node)
268 node = arr[node << 2 | 1]
269 self._propagate(node)
270 self._splay(path, 0)
271 return node
272
273 def reserve(self, n: int) -> None:
274 self.data.reserve(n)
275
276 def merge(self, other: "ReversibleLazySplayTreeArray") -> None:
277 assert self.data is other.data
278 if not other.root:
279 return
280 if not self.root:
281 self.root = other.root
282 return
283 self.root = self._right_splay(self.root)
284 self.data.arr[self.root << 2 | 1] = other.root
285 self._update(self.root)
286
287 def split(
288 self, k: int
289 ) -> tuple["ReversibleLazySplayTreeArray", "ReversibleLazySplayTreeArray"]:
290 assert (
291 -len(self) < k <= len(self)
292 ), f"IndexError: ReversibleLazySplayTreeArray.split({k}), len={len(self)}"
293 if k < 0:
294 k += len(self)
295 if k >= self.data.arr[self.root << 2 | 2]:
296 return self, ReversibleLazySplayTreeArray(self.data, _root=0)
297 self.root = self._kth_elm_splay(self.root, k)
298 left = ReversibleLazySplayTreeArray(
299 self.data, _root=self.data.arr[self.root << 2]
300 )
301 self.data.arr[self.root << 2] = 0
302 self._update(self.root)
303 return left, self
304
305 def _internal_split(self, k: int) -> tuple[int, int]:
306 if k >= self.data.arr[self.root << 2 | 2]:
307 return self.root, 0
308 self.root = self._kth_elm_splay(self.root, k)
309 left = self.data.arr[self.root << 2]
310 self._propagate(left)
311 self.data.arr[self.root << 2] = 0
312 self._update(self.root)
313 return left, self.root
314
315 def reverse(self, l: int, r: int) -> None:
316 assert (
317 0 <= l <= r <= len(self)
318 ), f"IndexError: ReversibleLazySplayTreeArray.reverse({l}, {r}), len={len(self)}"
319 if l == r:
320 return
321 data = self.data
322 left, right = self._internal_split(r)
323 if l:
324 left = self._kth_elm_splay(left, l - 1)
325 data.arr[(data.arr[left << 2 | 1] if l else left) << 2 | 3] ^= 1
326 if right:
327 data.arr[right << 2] = left
328 self._update(right)
329 self.root = right if right else left
330
331 def all_reverse(self) -> None:
332 self.data.arr[self.root << 2 | 3] ^= 1
333 self._propagate(self.root)
334
335 def apply(self, l: int, r: int, f: F) -> None:
336 assert (
337 0 <= l <= r <= len(self)
338 ), f"IndexError: ReversibleLazySplayTreeArray.apply({l}, {r}), len={len(self)}"
339 data = self.data
340 left, right = self._internal_split(r)
341 keydata, lazy = data.keydata, data.lazy
342 if l:
343 left = self._kth_elm_splay(left, l - 1)
344 node = data.arr[left << 2 | 1] if l else left
345 keydata[node * 3 + 0] = data.mapping(f, keydata[node * 3 + 0])
346 keydata[node * 3 + 1] = data.mapping(f, keydata[node * 3 + 1])
347 keydata[node * 3 + 2] = data.mapping(f, keydata[node * 3 + 2])
348 lazy[node] = data.composition(f, lazy[node])
349 if l:
350 self._update(left)
351 if right:
352 data.arr[right << 2] = left
353 self._update(right)
354 self.root = right if right else left
355
356 def all_apply(self, f: F) -> None:
357 if not self.root:
358 return
359 data, node = self.data, self.root
360 data.keydata[node * 3 + 0] = data.mapping(f, data.keydata[node * 3 + 0])
361 data.keydata[node * 3 + 1] = data.mapping(f, data.keydata[node * 3 + 1])
362 data.keydata[node * 3 + 2] = data.mapping(f, data.keydata[node * 3 + 2])
363 data.lazy[node] = data.composition(f, data.lazy[node])
364
365 def prod(self, l: int, r: int) -> T:
366 assert (
367 0 <= l <= r <= len(self)
368 ), f"IndexError: LazySplayTree.prod({l}, {r}), len={len(self)}"
369 data = self.data
370 left, right = self._internal_split(r)
371 if l:
372 left = self._kth_elm_splay(left, l - 1)
373 node = data.arr[left << 2 | 1] if l else left
374 self._propagate(node)
375 res = data.keydata[node * 3 + 1]
376 if right:
377 data.arr[right << 2] = left
378 self._update(right)
379 self.root = right if right else left
380 return res
381
382 def all_prod(self) -> T:
383 return self.data.keydata[self.root * 3 + 1]
384
385 def insert(self, k: int, key: T) -> None:
386 assert (
387 -len(self) <= k <= len(self)
388 ), f"IndexError: ReversibleLazySplayTreeArray.insert({k}, {key}), len={len(self)}"
389 if k < 0:
390 k += len(self)
391 data = self.data
392 node = self._make_node(key)
393 if not self.root:
394 self._update(node)
395 self.root = node
396 return
397 arr = data.arr
398 if k == data.arr[self.root << 2 | 2]:
399 arr[node << 2] = self._right_splay(self.root)
400 else:
401 node_ = self._kth_elm_splay(self.root, k)
402 if arr[node_ << 2]:
403 arr[node << 2] = arr[node_ << 2]
404 arr[node_ << 2] = 0
405 self._update(node_)
406 arr[node << 2 | 1] = node_
407 self._update(node)
408 self.root = node
409
410 def append(self, key: T) -> None:
411 data = self.data
412 node = self._right_splay(self.root)
413 self.root = self._make_node(key)
414 data.arr[self.root << 2] = node
415 self._update(self.root)
416
417 def appendleft(self, key: T) -> None:
418 node = self._left_splay(self.root)
419 self.root = self._make_node(key)
420 self.data.arr[self.root << 2 | 1] = node
421 self._update(self.root)
422
423 def pop(self, k: int = -1) -> T:
424 assert (
425 -len(self) <= k < len(self)
426 ), f"IndexError: ReversibleLazySplayTreeArray.pop({k})"
427 data = self.data
428 if k == -1:
429 node = self._right_splay(self.root)
430 self._propagate(node)
431 self.root = data.arr[node << 2]
432 return data.keydata[node * 3 + 0]
433 self.root = self._kth_elm_splay(self.root, k)
434 res = data.keydata[self.root * 3 + 0]
435 if not data.arr[self.root << 2]:
436 self.root = data.arr[self.root << 2 | 1]
437 elif not data.arr[self.root << 2 | 1]:
438 self.root = data.arr[self.root << 2]
439 else:
440 node = self._right_splay(data.arr[self.root << 2])
441 data.arr[node << 2 | 1] = data.arr[self.root << 2 | 1]
442 self.root = node
443 self._update(self.root)
444 return res
445
446 def popleft(self) -> T:
447 assert self, "IndexError: ReversibleLazySplayTreeArray.popleft()"
448 node = self._left_splay(self.root)
449 self.root = self.data.arr[node << 2 | 1]
450 return self.data.keydata[node * 3 + 0]
451
452 def rotate(self, x: int) -> None:
453 # 「末尾をを削除し先頭に挿入」をx回
454 n = self.data.arr[self.root << 2 | 2]
455 l, self = self.split(n - (x % n))
456 self.merge(l)
457
458 def tolist(self) -> list[T]:
459 node = self.root
460 arr, keydata = self.data.arr, self.data.keydata
461 stack = []
462 res = []
463 while stack or node:
464 if node:
465 self._propagate(node)
466 stack.append(node)
467 node = arr[node << 2]
468 else:
469 node = stack.pop()
470 res.append(keydata[node * 3 + 0])
471 node = arr[node << 2 | 1]
472 return res
473
474 def clear(self) -> None:
475 self.root = 0
476
477 def __setitem__(self, k: int, key: T):
478 assert (
479 -len(self) <= k < len(self)
480 ), f"IndexError: ReversibleLazySplayTreeArray.__setitem__({k})"
481 self.root = self._kth_elm_splay(self.root, k)
482 self.data.keydata[self.root * 3 + 0] = key
483 self._update(self.root)
484
485 def __getitem__(self, k: int) -> T:
486 assert (
487 -len(self) <= k < len(self)
488 ), f"IndexError: ReversibleLazySplayTreeArray.__getitem__({k})"
489 self.root = self._kth_elm_splay(self.root, k)
490 return self.data.keydata[self.root * 3 + 0]
491
492 def __iter__(self):
493 self.__iter = 0
494 return self
495
496 def __next__(self):
497 if self.__iter == self.data.arr[self.root << 2 | 2]:
498 raise StopIteration
499 res = self.__getitem__(self.__iter)
500 self.__iter += 1
501 return res
502
503 def __reversed__(self):
504 for i in range(len(self)):
505 yield self.__getitem__(-i - 1)
506
507 def __len__(self):
508 return self.data.arr[self.root << 2 | 2]
509
510 def __str__(self):
511 return str(self.tolist())
512
513 def __bool__(self):
514 return self.root != 0
515
516 def __repr__(self):
517 return f"ReversibleLazySplayTreeArray({self})"
518from typing import Optional, Final
519import random
520import string
521
522_titan_pylib_DynamicHashString_MOD: Final[int] = (1 << 61) - 1
523_titan_pylib_DynamicHashString_DIC: Final[dict[str, int]] = {
524 c: i for i, c in enumerate(string.ascii_lowercase, 1)
525}
526_titan_pylib_DynamicHashString_MASK30: Final[int] = (1 << 30) - 1
527_titan_pylib_DynamicHashString_MASK31: Final[int] = (1 << 31) - 1
528_titan_pylib_DynamicHashString_MASK61: Final[int] = _titan_pylib_DynamicHashString_MOD
529
530
531class DynamicHashStringBase:
532 """動的な文字列に対するロリハです。
533
534 平衡二分木にモノイドを載せてるだけです。こんなライブラリ必要ないです。
535
536 Example:
537 ```
538 base = DynamicHashStringBase(2 * 10**5 + 1)
539 dhs_s = DynamicHashString(base, s)
540 dhs_t = DynamicHashString(base, t)
541
542 pref = dhs_s.get(0, r)
543 suff = dhs_t.get(l, n)
544 h = base.unite(pref, suff, n-l)
545 ```
546 """
547
548 def __init__(self, n: int = 0, base: int = -1, seed: Optional[int] = None) -> None:
549 assert n >= 0
550 rand = random.Random(seed)
551 base = rand.randint(37, 10**9) if base < 0 else base
552 powb = [1] * (n + 1)
553 for i in range(1, n + 1):
554 powb[i] = self.get_mul(powb[i - 1], base)
555 op = lambda s, t: (self.unite(s[0], t[0], t[1]), s[1] + t[1])
556 e = (0, 0)
557 self.base = base
558 self.data = ReversibleLazySplayTreeArrayData(op=op, e=e)
559 self.n = n
560 self.powb = powb
561
562 @staticmethod
563 def get_mul(a: int, b: int) -> int:
564 au = a >> 31
565 ad = a & _titan_pylib_DynamicHashString_MASK31
566 bu = b >> 31
567 bd = b & _titan_pylib_DynamicHashString_MASK31
568 mid = ad * bu + au * bd
569 midu = mid >> 30
570 midd = mid & _titan_pylib_DynamicHashString_MASK30
571 return DynamicHashStringBase.get_mod(
572 au * bu * 2 + midu + (midd << 31) + ad * bd
573 )
574
575 @staticmethod
576 def get_mod(x: int) -> int:
577 # 商と余りを計算して足す->割る
578 xu = x >> 61
579 xd = x & _titan_pylib_DynamicHashString_MASK61
580 res = xu + xd
581 if res >= _titan_pylib_DynamicHashString_MOD:
582 res -= _titan_pylib_DynamicHashString_MOD
583 return res
584
585 def extend(self, cap: int) -> None:
586 pre_cap = len(self.powb)
587 powb = self.powb
588 powb += [0] * cap
589 for i in range(pre_cap, pre_cap + cap):
590 powb[i] = DynamicHashStringBase.get_mul(powb[i - 1], self.base)
591
592 def get_cap(self) -> int:
593 return len(self.powb)
594
595 def unite(self, h1: int, h2: int, k: int) -> int:
596 """2つの hash 値を concat します。
597
598 Args:
599 h1 (int): prefix
600 h2 (int): suffix
601 k (int): h2の長さ
602
603 Returns:
604 int: h1 + h2
605 """
606 # h1, h2, k
607 # len(h2) == k
608 # h1 <- h2
609 if k >= self.get_cap():
610 self.extend(k - self.get_cap() + 1)
611 return self.get_mod(self.get_mul(h1, self.powb[k]) + h2)
612
613
614class DynamicHashString:
615
616 def __init__(self, hsb: DynamicHashStringBase, s: str) -> None:
617 self.hsb = hsb
618 self.splay: ReversibleLazySplayTreeArray[tuple[int, int], None] = (
619 ReversibleLazySplayTreeArray(
620 hsb.data, ((_titan_pylib_DynamicHashString_DIC[c], 1) for c in s)
621 )
622 )
623
624 def insert(self, k: int, c: str) -> None:
625 """位置 ``k`` に ``c`` を挿入します。
626 :math:`O(\\log{n})` です。
627 """
628 self.splay.insert(k, (_titan_pylib_DynamicHashString_DIC[c], 1))
629
630 def pop(self, k: int) -> int:
631 return self.splay.pop(k)
632
633 def reverse(self, l: int, r: int) -> None:
634 self.splay.reverse(l, r)
635
636 def all_reverse(self) -> None:
637 self.splay.all_reverse()
638
639 def split(self, k: int) -> tuple["DynamicHashString", "DynamicHashString"]:
640 left, right = self.splay.split(k)
641 return (DynamicHashString(self.hsb, left), DynamicHashString(self.hsb, right))
642
643 def all_get(self) -> int:
644 return self.splay.all_prod()[0]
645
646 def get(self, l: int, r: int) -> int:
647 return self.splay.prod(l, r)[0]
648
649 def extend(self, other: "DynamicHashString") -> None:
650 assert self.hsb is other.hsb
651 self.splay.merge(other.splay)
652
653 def __getitem__(self, k: int) -> int:
654 return self.splay[k][0]
655
656 def set(self, k: int, c: str) -> None:
657 self.splay[k] = (_titan_pylib_DynamicHashString_DIC[c], 1)
658
659 def __setitem__(self, k: int, c: str) -> None:
660 return self.set(k, c)
661
662 def __len__(self) -> int:
663 return len(self.splay)
664
665 def __str__(self) -> str:
666 return str([self[i] for i in range(len(self))])
仕様¶
- class DynamicHashString(hsb: DynamicHashStringBase, s: str)[source]¶
Bases:
object- extend(other: DynamicHashString) None[source]¶
- split(k: int) tuple[DynamicHashString, DynamicHashString][source]¶
- class DynamicHashStringBase(n: int = 0, base: int = -1, seed: int | None = None)[source]¶
Bases:
object動的な文字列に対するロリハです。
平衡二分木にモノイドを載せてるだけです。こんなライブラリ必要ないです。
Example
``` base = DynamicHashStringBase(2 * 10**5 + 1) dhs_s = DynamicHashString(base, s) dhs_t = DynamicHashString(base, t)
pref = dhs_s.get(0, r) suff = dhs_t.get(l, n) h = base.unite(pref, suff, n-l) ```