ধরুন আমাদের একটি ছোট হাতের স্ট্রিং s আছে, আমাদেরকে s-এ কমপক্ষে দুইবার হওয়া দীর্ঘতম সাবস্ট্রিংয়ের দৈর্ঘ্য খুঁজে বের করতে হবে। যদি আমরা এই ধরনের স্ট্রিং খুঁজে না পাই, 0 ফেরত দিন।
সুতরাং, যদি ইনপুটটি s ="abdgoalputabdtypeabd" এর মত হয়, তাহলে আউটপুট হবে 3, কারণ দীর্ঘতম সাবস্ট্রিং যা একাধিকবার হয় তা হল "abd"।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন lcs() সংজ্ঞায়িত করুন। এটি s1, s2 লাগবে৷
- n :=সর্বনিম্ন আকার s1 এবং আকার s2
- আমি 0 থেকে n - 1 রেঞ্জের জন্য, কর
- যদি s1[i] s2[i] এর মত না হয়, তাহলে
- s1-এর রিটার্ন সাবস্ট্রিং[সূচী 0 থেকে i-1]
- যদি s1[i] s2[i] এর মত না হয়, তাহলে
- s1-এর রিটার্ন সাবস্ট্রিং[সূচী 0 থেকে n - 1]
- প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
- প্রত্যয় :=একটি নতুন তালিকা
- n :=s এর আকার
- max_len :=0
- আমি 0 থেকে n - 1 রেঞ্জের জন্য, কর
- প্রত্যয় শেষে সন্নিবেশ করান (s[সূচী i থেকে n - 1] এর সাবস্ট্রিং)
- তালিকা প্রত্যয়গুলি সাজান
- প্রতিটি আইটেমের জন্য a থেকে প্রত্যয় এবং b প্রত্যয়গুলির সাবস্ট্রিং থেকে [সূচী 1 থেকে শেষ পর্যন্ত], করুন
- rtr :=lcs(a, b)
- যদি rtr> max_len এর আকার হয়, তাহলে
- max_len :=rtr এর আকার
- প্রত্যাবর্তন max_len
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def lcs(s1, s2): n = min(len(s1), len(s2)) for i in range(n): if s1[i] != s2[i]: return s1[:i] return s1[:n] def solve(s): suffixes = [] n = len(s) max_len = 0 for i in range(n): suffixes.append(s[i:n]) suffixes.sort() for a, b in zip(suffixes, suffixes[1:]): rtr = lcs(a, b) if len(rtr) > max_len: max_len = len(rtr) return max_len s = "abdgoalputabdtypeabd" print(solve(s))
ইনপুট
"abdgoalputabdtypeabd"
আউটপুট
3
