Giả sử chúng ta được cung cấp n số chuỗi; str1, str2, str3, ....., strn. Bây giờ, giả sử rằng substri là một tập hợp chứa tất cả các chuỗi con của stri. Hợp nhất của tất cả các tập hợp là substr_union. Bây giờ chúng ta nhận được q số truy vấn và chúng ta phải tìm phần tử thứ q của tập hợp substr_union. Tập hợp substr_union được sắp xếp theo từ điển và các chỉ mục bắt đầu từ 1.
Vì vậy, nếu đầu vào giống như danh sách các chuỗi là =['pqr', 'pqt'], các truy vấn là =[4, 7, 9], thì đầu ra sẽ là ['pqt', 'qt', 't' ]
Các chuỗi con từ chuỗi đầu tiên là subs_str_1 ={p, pq, pqr, q, qr, r}, sub_str_2 ={p, pq, pqt, q, qt, t}.
Sự kết hợp của hai tập hợp này, hoặc substr_union là {p, pq, pqr, pqt, q, qr, qt, r, t}.
Vì vậy, các mục ở chỉ mục 4, 7 và 9 lần lượt là 'pqt', qt 'và' t '.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Định nghĩa một hàm lng_i (). Điều này sẽ mất đủ, lng, i
- d:=một tuple mới chứa (đủ, lng)
- lo:=0
- chào:=0
- cho mỗi tuple (suf, lng) trong d, do
- nếu lng tương tự như null, thì
- lng:=0
- hi:=hi + size của suf - lng
- nếu hi - 1 giống với i, thì
- trả về suf
- ngược lại khi hi - 1> i, thì
- đối với chỉ mục p và mục q trong danh sách các giá trị từ lng đến kích thước của suf, hãy thực hiện
- nếu lo + p giống với i, thì
- trả về suf [từ chỉ mục 0 đến j + 1]
- nếu lo + p giống với i, thì
- đối với chỉ mục p và mục q trong danh sách các giá trị từ lng đến kích thước của suf, hãy thực hiện
- lo:=xin chào
- nếu lng tương tự như null, thì
- trả về Sai
- Định nghĩa một hàm hlp_ii (). Điều này sẽ lấy str1, str2
- ub:=kích thước tối thiểu của str1, kích thước của str2
- cnt:=0
- đối với tôi trong phạm vi từ 0 đến ub, thực hiện
- nếu str1 [i] giống với str2 [i], thì
- cnt:=cnt + 1
- nếu không,
- trả về cnt
- trả về cnt
- nếu str1 [i] giống với str2 [i], thì
- t_dict:=một bản đồ mới
- đủ:=một danh sách mới
- lng:=một danh sách mới
- đối với mỗi str trong chuỗi, thực hiện
-
đối với tôi trong phạm vi từ 0 đến kích thước của str, làm
- giá trị:=str [từ chỉ mục i đến cuối]
- nếu giá trị không có trong t_dict, thì
- t_dict [value]:=1
- chèn giá trị vào cuối hậu tố
-
- sắp xếp danh sách đủ
- Suff_len:=kích thước của đủ
- đối với tôi trong phạm vi từ 0 đến kích thước của Suff_len, hãy thực hiện
- nếu tôi giống 0, thì
- chèn null vào cuối lng
- nếu không,
- chèn hlp_ii (đủ [i-1], đủ [i]) vào cuối lng
- nếu tôi giống 0, thì
- res:=một danh sách mới
- đối với mỗi q trong q_list, thực hiện
- chèn (lng_i (đủ, lng, q-1)) vào cuối res
- trả lại res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def lng_i(suff, lng, i):
d = zip(suff,lng)
lo = hi = 0
for suf, lng in d:
if lng is None:
lng = 0
hi += len(suf) - lng
if hi - 1 == i:
return suf
elif hi - 1 > i:
for p, q in enumerate(list(range(lng, len(suf)))):
if lo + p == i:
return suf[:q+1]
lo = hi
return False
def hlp_ii(str1,str2):
ub = min(len(str1), len(str2))
cnt = 0
for i in range(ub):
if str1[i] == str2[i]:
cnt += 1
else:
return cnt
return cnt
def solve(strings,q_list):
t_dict = {}
suff = []
lng = []
for str in strings:
for i in range(len(str)):
value = str[i:]
if value not in t_dict:
t_dict[value] = 1
suff.append(value)
suff.sort()
suff_len = len(suff)
for i in range(suff_len):
if i == 0:
lng.append(None)
else:
lng.append(hlp_ii(suff[i-1], suff[i]))
res = []
for q in q_list:
(res.append(lng_i(suff, lng, q-1)))
return res
print(solve(['pqr', 'pqt'], [4, 7, 9])) Đầu vào
['pqr', 'pqt'], [4, 7, 9]
Đầu ra
['pqt', 'qt', 't']