1# ref: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
2from titan_pylib.data_structures.segment_tree.segment_tree import SegmentTree
3from typing import Optional, Final
4import random
5import string
6
7_titan_pylib_HashString_MOD: Final[int] = (1 << 61) - 1
8_titan_pylib_HashString_DIC: Final[dict[str, int]] = {
9 c: i for i, c in enumerate(string.ascii_lowercase, 1)
10}
11_titan_pylib_HashString_MASK30: Final[int] = (1 << 30) - 1
12_titan_pylib_HashString_MASK31: Final[int] = (1 << 31) - 1
13_titan_pylib_HashString_MASK61: Final[int] = _titan_pylib_HashString_MOD
14
15
[docs]
16class HashStringBase:
17 """HashStringのベースクラスです。"""
18
19 def __init__(self, n: int = 0, base: int = -1, seed: Optional[int] = None) -> None:
20 """
21 :math:`O(n)` です。
22
23 Args:
24 n (int): 文字列の長さの上限です。上限を超えても問題ありません。
25 base (int, optional): Defaults to -1.
26 seed (Optional[int], optional): Defaults to None.
27 """
28 rand = random.Random(seed)
29 base = rand.randint(37, 10**9) if base < 0 else base
30 powb = [1] * (n + 1)
31 invb = [1] * (n + 1)
32 invbpow = pow(base, -1, _titan_pylib_HashString_MOD)
33 for i in range(1, n + 1):
34 powb[i] = HashStringBase.get_mul(powb[i - 1], base)
35 invb[i] = HashStringBase.get_mul(invb[i - 1], invbpow)
36 self.n = n
37 self.base = base
38 self.invpow = invbpow
39 self.powb = powb
40 self.invb = invb
41
[docs]
42 @staticmethod
43 def get_mul(a: int, b: int) -> int:
44 au = a >> 31
45 ad = a & _titan_pylib_HashString_MASK31
46 bu = b >> 31
47 bd = b & _titan_pylib_HashString_MASK31
48 mid = ad * bu + au * bd
49 midu = mid >> 30
50 midd = mid & _titan_pylib_HashString_MASK30
51 return HashStringBase.get_mod(au * bu * 2 + midu + (midd << 31) + ad * bd)
52
[docs]
53 @staticmethod
54 def get_mod(x: int) -> int:
55 xu = x >> 61
56 xd = x & _titan_pylib_HashString_MASK61
57 res = xu + xd
58 if res >= _titan_pylib_HashString_MOD:
59 res -= _titan_pylib_HashString_MOD
60 return res
61
[docs]
62 def extend(self, cap: int) -> None:
63 pre_cap = len(self.powb)
64 powb, invb = self.powb, self.invb
65 powb += [0] * cap
66 invb += [0] * cap
67 invbpow = pow(self.base, -1, _titan_pylib_HashString_MOD)
68 for i in range(pre_cap, pre_cap + cap):
69 powb[i] = HashStringBase.get_mul(powb[i - 1], self.base)
70 invb[i] = HashStringBase.get_mul(invb[i - 1], invbpow)
71
[docs]
72 def get_cap(self) -> int:
73 return len(self.powb)
74
[docs]
75 def unite(self, h1: int, h2: int, k: int) -> int:
76 # len(h2) == k
77 # h1 <- h2
78 if k >= self.get_cap():
79 self.extend(k - self.get_cap() + 1)
80 return self.get_mod(self.get_mul(h1, self.powb[k]) + h2)
81
82
[docs]
83class HashString:
84
85 def __init__(self, hsb: HashStringBase, s: str, update: bool = False) -> None:
86 """ロリハを構築します。
87 :math:`O(n)` です。
88
89 Args:
90 hsb (HashStringBase): ベースクラスです。
91 s (str): ロリハを構築する文字列です。
92 update (bool, optional): ``update=True`` のとき、1点更新が可能になります。
93 """
94 n = len(s)
95 data = [0] * n
96 acc = [0] * (n + 1)
97 if n >= hsb.get_cap():
98 hsb.extend(n - hsb.get_cap() + 1)
99 powb = hsb.powb
100 for i, c in enumerate(s):
101 data[i] = hsb.get_mul(powb[n - i - 1], _titan_pylib_HashString_DIC[c])
102 acc[i + 1] = hsb.get_mod(acc[i] + data[i])
103 self.hsb = hsb
104 self.n = n
105 self.acc = acc
106 self.used_seg = False
107 if update:
108 self.seg = SegmentTree(
109 data, lambda s, t: (s + t) % _titan_pylib_HashString_MOD, 0
110 )
111
[docs]
112 def get(self, l: int, r: int) -> int:
113 """``s[l, r)`` のハッシュ値を返します。
114 1点更新処理後は :math:`O(\\log{n})` 、そうでなければ :math:`O(1)` です。
115
116 Args:
117 l (int): インデックスです。
118 r (int): インデックスです。
119
120 Returns:
121 int: ハッシュ値です。
122 """
123 assert 0 <= l <= r <= self.n
124 if self.used_seg:
125 return self.hsb.get_mul(self.seg.prod(l, r), self.hsb.invb[self.n - r])
126 return self.hsb.get_mul(
127 self.hsb.get_mod(self.acc[r] - self.acc[l]), self.hsb.invb[self.n - r]
128 )
129
[docs]
130 def __getitem__(self, k: int) -> int:
131 """``s[k]`` のハッシュ値を返します。
132 1点更新処理後は :math:`O(\\log{n})` 、そうでなければ :math:`O(1)` です。
133
134 Args:
135 k (int): インデックスです。
136
137 Returns:
138 int: ハッシュ値です。
139 """
140 return self.get(k, k + 1)
141
[docs]
142 def set(self, k: int, c: str) -> None:
143 """`k` 番目の文字を `c` に更新します。
144 :math:`O(\\log{n})` です。また、今後の ``get()`` が :math:`O(\\log{n})` になります。
145
146 Args:
147 k (int): インデックスです。
148 c (str): 更新する文字です。
149 """
150 self.used_seg = True
151 self.seg[k] = self.hsb.get_mul(
152 self.hsb.powb[self.n - k - 1], _titan_pylib_HashString_DIC[c]
153 )
154
155 def __setitem__(self, k: int, c: str) -> None:
156 return self.set(k, c)
157
158 def __len__(self):
159 return self.n
160
[docs]
161 def get_lcp(self) -> list[int]:
162 """lcp配列を返します。
163 :math:`O(n\\log{n})` です。
164 """
165 a = [0] * self.n
166 memo = [-1] * (self.n + 1)
167 for i in range(self.n):
168 ok, ng = 0, self.n - i + 1
169 while ng - ok > 1:
170 mid = (ok + ng) >> 1
171 if memo[mid] == -1:
172 memo[mid] = self.get(0, mid)
173 if memo[mid] == self.get(i, i + mid):
174 ok = mid
175 else:
176 ng = mid
177 a[i] = ok
178 return a