ধরুন আমরা n নম্বর স্ট্রিং প্রদান করেছি; str1, str2, str3,.....,strn. এখন, ধরুন যে substri হল একটি সেট যাতে স্ট্রির সমস্ত সাবস্ট্রিং রয়েছে। সমস্ত সাবস্ট্র সেটের মিলন হল substr_union। আমাদের এখন প্রশ্নগুলির q নম্বর দেওয়া হয়েছে, এবং আমাদের সেট substr_union-এর q-th উপাদান খুঁজে বের করতে হবে। সেট substr_union অভিধানিকভাবে সাজানো হয়েছে এবং সূচীগুলি 1 থেকে শুরু হয়।
সুতরাং, যদি ইনপুটটি স্ট্রিংগুলির তালিকার মতো হয় =['pqr', 'pqt'], প্রশ্নগুলি =[4, 7, 9], তাহলে আউটপুট হবে ['pqt', 'qt', 't' ]
প্রথম স্ট্রিং থেকে সাবস্ট্রিংগুলি হল subs_str_1 ={p, pq, pqr, q, qr, r }, sub_str_2 ={p, pq, pqt, q, qt, t}।
এই দুটি সেটের মিলন, বা substr_union হল {p, pq, pqr, pqt, q, qr, qt, r, t}।
সুতরাং সূচক 4, 7, এবং 9 এ আইটেমগুলি যথাক্রমে 'pqt', qt' এবং 't'।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন সংজ্ঞায়িত করুন lng_i()। এটি suff, lng, i
- লাগবে
- d :=একটি নতুন টিপল যাতে রয়েছে (suff, lng)
- lo :=0
- হাই :=0
- প্রতিটি টিপলের জন্য (suf, lng) d, do
- যদি lng null এর মত হয়, তাহলে
- lng :=0
- hi :=hi + suf - lng এর আকার
- যদি hi - 1 i এর মত হয়, তাহলে
- সুফ ফেরত
- অন্যথায় যখন hi - 1> i, তারপর
- lng থেকে suf এর আকার পর্যন্ত মানের তালিকায় সূচী p এবং আইটেম q এর জন্য, করুন
- যদি lo + p হয় i এর মতো, তাহলে
- সাফ [সূচক 0 থেকে j+1] ফেরত দিন
- যদি lo + p হয় i এর মতো, তাহলে
- যদি lng null এর মত হয়, তাহলে
- lo :=হাই
- মিথ্যে ফেরত দিন
- লাগবে
- ub :=str1 এর ন্যূনতম আকার, str2 এর আকার
- cnt :=0
- আমি 0 থেকে ub এর মধ্যে, কর
- যদি str1[i] str2[i] এর মত হয়, তাহলে
- cnt :=cnt + 1
- অন্যথায়,
- cnt ফেরত
- cnt ফেরত
- যদি str1[i] str2[i] এর মত হয়, তাহলে
-
আমি 0 থেকে str এর আকারের মধ্যে, কর
- মান :=str[সূচী i থেকে শেষ পর্যন্ত]
- যদি t_dict-এ মান উপস্থিত না থাকে, তাহলে
- t_dict[মান] :=1
- suff-এর শেষে মান সন্নিবেশ করান
- যদি আমি 0 এর মত হয়, তাহলে
- lng-এর শেষে নাল ঢোকান
- অন্যথায়,
- lng-এর শেষে hlp_ii(suff[i-1], suff[i]) ঢোকান
- res এর শেষে সন্নিবেশ করুন (lng_i(suff, lng, q-1))
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
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])) ইনপুট
['pqr', 'pqt'], [4, 7, 9]
আউটপুট
['pqt', 'qt', 't']
