পাইথনে একটি স্ট্রিং-এ সর্বোচ্চ দৈর্ঘ্যের পুনরাবৃত্ত সাবস্ট্রিং খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি লোয়ারকেস স্ট্রিং s আছে। আমাদের এমন সবচেয়ে লম্বা সাবস্ট্রিং খুঁজে বের করতে হবে যা স্ট্রিং-এ কমপক্ষে দুবার 나와য়। যদি এমন কোনো সাবস্ট্রিং না থাকে, তবে 0 রিটার্ন করুন।

উদাহরণস্বরূপ, ইনপুট s = "abdgoalputabdtypeabd" হলে আউটপুট হবে 3, কারণ "abd" সবচেয়ে লম্বা সাবস্ট্রিং যা একাধিকবার উপস্থিত।

সমাধানের পদ্ধতি

সফিক্স অ্যারে (suffix array) এবং লংগেস্ট কমন প্রিফিক্স (LCP) ধারণা ব্যবহার করে সমাধান করা হয়।

1. LCS ফাংশন: দুটি স্ট্রিংয়ের লংগেস্ট কমন প্রিফিক্স বের করুন।
2. সফিক্স তৈরি: স্ট্রিং-এর সব সফিক্স সংগ্রহ করুন।
3. সর্ট করুন: সফিক্সগুলো লেক্সিকোগ্রাফিক্যালি সর্ট করুন।
4. সন্নিহিত সফিক্স তুলনা: সর্ট করা সফিক্সের প্রতিটি সন্নিহিত জোড়ার LCS বের করুন এবং সর্বোচ্চ দৈর্ঘ্য ট্র্যাক করুন।

পাইথন কোড

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))  # আউটপুট: 3

সময় জটিলতা

O(n² log n) - সফিক্স তৈরি ও সর্ট করার কারণে। বড় স্ট্রিংয়ের জন্যSuffix Array বা Suffix Automaton ব্যবহার করলে O(n) সম্ভব।