1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
import random
from bisect import bisect_left
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)
setrecursionlimit(int(2e9))
class Arr:
array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
graph = staticmethod(lambda size=N: [[] for _ in range(size)])
class Math:
max = staticmethod(lambda a, b: a if a > b else b)
min = staticmethod(lambda a, b: a if a < b else b)
class Std:
class StringHash:
"""A class for efficiently computing hash values of substrings within a string."""
def __init__(self, s: str, mod: int = 1_070_777_777):
"""Initialize the StringHash object with the string, base, and mod."""
self._mod = mod
self._base = random.randint(8 * 10 ** 8, 9 * 10 ** 8)
self._s = s
self._n = len(s)
self._pow_base_ = [1] + Arr.array(0, self._n)
self._pre_hash_ = Arr.array(0, self._n + 1)
self._compute_hash()
def _compute_hash(self):
"""Compute the prefix hash values and power of base values for the string."""
for i, b in enumerate(self._s):
self._pow_base_[i + 1] = self._pow_base_[i] * self._base % self._mod
self._pre_hash_[i + 1] = (self._pre_hash_[i] * self._base + ord(b)) % self._mod
def get_hash(self, l: int, r: int) -> int:
"""Get the hash value of the substring s[l:r] """
return (self._pre_hash_[r + 1] - self._pre_hash_[l] * self._pow_base_[r - l + 1] % self._mod + self._mod) % self._mod
def compute_hash(self, word: str) -> int:
"""Compute the hash value of a given word using the object's base and mod."""
h = 0
for b in word:
h = (h * self._base + ord(b)) % self._mod
return h
class Solution:
def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
s_hash = Std.StringHash(s)
a_id_, b_id_ = [], []
a_hash, b_hash = s_hash.compute_hash(a), s_hash.compute_hash(b)
for i in range(len(s)):
if i + len(a) <= len(s) and a_hash == s_hash.get_hash(i, i + len(a) - 1):
a_id_.append(i)
if i + len(b) <= len(s) and b_hash == s_hash.get_hash(i, i + len(b) - 1):
b_id_.append(i)
ans = []
if not (a_id_ and b_id_):
return []
for i in a_id_:
ans_l, ans_r = 0, 0
l, r = 0, len(b_id_) - 1
while l < r:
mid = l + r >> 1
if b_id_[mid] >= i - k:
r = mid
else:
l = mid + 1
ans_l = r if b_id_[r] >= i - k else INF
l, r = 0, len(b_id_) - 1
while l < r:
mid = l + r + 1 >> 1
if b_id_[mid] <= i + k:
l = mid
else:
r = mid - 1
ans_r = r if b_id_[r] <= i + k else -INF
if ans_r >= ans_l:
ans.append(i)
return ans
print(Solution().beautifulIndices("vatevavakz", "va", "lbda", 1))
|