สมมติว่ามี n สตริง str1..strn ให้ substr_i เป็นเซตของทุก substring ของ stri ยูเนียนของทั้งหมดคือ substr_union เรียงตามลำดับเล็กซิโคกราฟิก ให้ q queries หา q-th element ของ substr_union (1-indexed)
ตัวอย่าง strings = ['pqr', 'pqt'], queries = [4, 7, 9] ผลลัพธ์ = ['pqt', 'qt', 't']
ขั้นตอนการแก้ปัญหา
- รวบรวม suffix ทั้งหมดของทุกสตริง ลบซ้ำ เรียงลำดับ
- คำนวณ LCP (Longest Common Prefix) ระหว่าง suffix ติดกัน
- แต่ละ suffix ให้ substring ใหม่จำนวน len(suffix) - LCP กับ suffix ก่อนหน้า
- สะสมจำนวน substring จนถึง query index แล้วคืนค่า substring นั้น
ตัวอย่างโค้ด
def lng_i(suff, lng, i):
d = zip(suff, lng)
lo = hi = 0
for suf, lng_val in d:
if lng_val is None:
lng_val = 0
hi += len(suf) - lng_val
if hi - 1 == i:
return suf
elif hi - 1 > i:
for p, q in enumerate(range(lng_val, 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 s in strings:
for i in range(len(s)):
value = s[i:]
if value not in t_dict:
t_dict[value] = 1
suff.append(value)
suff.sort()
for i in range(len(suff)):
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]))
อินพุต
['pqr', 'pqt'], [4, 7, 9]
เอาต์พุต
['pqt', 'qt', 't']
