ধরুন আমাদের দুটি স্ট্রিং আছে s এবং t, এবং দুটি মান p এবং q। আমাদের পরীক্ষা করতে হবে যে s থেকে t পাওয়া সম্ভব কি না যাতে s কে p অক্ষরগুলির গ্রুপে বিভক্ত করা হয় শেষ গ্রুপটি ছাড়া যেটিতে ≤ p অক্ষর থাকবে এবং আমরা প্রতিটি গ্রুপ থেকে সর্বাধিক q সংখ্যক অক্ষর বাছাই করতে পারি, এবং এছাড়াও t-এ অক্ষরের ক্রম অবশ্যই s-এর মতই হতে হবে।
সুতরাং, যদি ইনপুটটি s ="mnonnopeqrst", t ="moprst", p =5, q =2 এর মতো হয়, তাহলে আউটপুটটি True হবে কারণ আমরা "mnonn", "opeqr", "st" এর মতো বিভাগ তৈরি করতে পারি। , এখন "mnonn" এবং "opeqr" থেকে 2টি ক্যারেক্টার সাবস্ট্রিং "mo" এবং "pr" নিয়ে তারপর "st" ইতিমধ্যেই আছে তাই এই দুটি দৈর্ঘ্যের সাবস্ট্রিং ব্যবহার করে আমরা সহজ সংযোজন দ্বারা t তৈরি করতে পারি।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- temp :=একটি খালি মানচিত্র যেখানে সমস্ত কীগুলির জন্য খালি তালিকা রয়েছে
- l :=s এর দৈর্ঘ্যের সমান আকারের একটি তালিকা এবং 0 দিয়ে পূরণ করুন
- 0 থেকে s আকারের রেঞ্জের জন্য,
- করুন
- টেম্পের শেষে i ঢোকান['a']
- কম :=0
- আমি 0 থেকে t - 1 এর পরিসরের জন্য, কর
- সূচক :=তাপমাত্রা['a']
- এটি :=সাজানো ক্রম বজায় রাখতে সূচক তালিকায় নিম্ন সন্নিবেশ করার জন্য সূচক
- যদি এটি সূচকের আকারের সমান হয় - 1, তাহলে
- মিথ্যে ফেরত দিন
- count :=(index[it] / p) এর ভাগফল
- l[count] :=l[count] + 1
- যদি l[count]>=q হয়, তাহলে
- গণনা :=গণনা + 1
- কম :=গণনা * p
- অন্যথায়,
- নিম্ন :=সূচক[এটি] + 1
- সত্য ফেরান
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
from bisect import bisect_left from collections import defaultdict def solve(s, t, b, m) : temp = defaultdict(list) l = [0] * len(s) for i in range(len(s)) : temp['a'].append(i) low = 0 for i in range(len(t)) : indices = temp['a'] it = bisect_left(indices, low) if it == len(indices) : return False count = indices[it] // b l[count] = l[count] + 1 if l[count] >= m : count += 1 low = count * b else : low = indices[it] + 1 return True s = "mnonnopeqrst" t = "moprst" p = 5 q = 2 print (solve(s, t, p, q))
ইনপুট
"mnonnopeqrst", "moprst", 5, 2
আউটপুট
True
