पायथन में किसी स्ट्रिंग में सबसे लंबे दोहराव वाले सबस्ट्रिंग की लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास एक लोअरकेस स्ट्रिंग s है, हमें उस सबसे लंबे सबस्ट्रिंग की लंबाई ढूंढनी है जो s में कम से कम दो बार आता है। यदि ऐसा कोई स्ट्रिंग नहीं मिलता, तो 0 लौटाएं।

उदाहरण के लिए, यदि इनपुट है s = "abdgoalputabdtypeabd", तो आउटपुट 3 होगा, क्योंकि सबसे लंबा सबस्ट्रिंग जो एक से अधिक बार आता है वह है "abd"।

एल्गोरिदम

1. lcs() फ़ंक्शन परिभाषित करें जो दो स्ट्रिंग्स s1, s2 लेता है और उनका सबसे लंबा कॉमन प्रीफिक्स लौटाता है।
2. स्ट्रिंग s के सभी सफिक्स की सूची बनाएं।
3. सफिक्स सूची को सॉर्ट करें।
4. आसन्न सफिक्स जोड़ियों की तुलना करके सबसे लंबा कॉमन प्रीफिक्स ढूंढें।
5. अधिकतम लंबाई लौटाएं।

उदाहरण कार्यान्वयन

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

इनपुट

"abdgoalputabdtypeabd"

आउटपुट

3