मान लीजिए कि हमारे पास एक लोअरकेस स्ट्रिंग 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 :=आकार का
- अधिकतम_लेन:=0
- मैं के लिए 0 से n -1 की सीमा में, करो
- प्रत्ययों के अंत में
- सम्मिलित करें (s[index i से n-1] तक का विकल्प)
- सूची प्रत्ययों को क्रमबद्ध करें
- प्रत्येक आइटम के लिए ए प्रत्यय से और बी प्रत्यय के सबस्ट्रिंग से [इंडेक्स 1 से अंत तक], करते हैं
- rtr :=lcs(a, b)
- यदि आरटीआर का आकार> max_len, तो
- max_len :=rtr का आकार
- अधिकतम_लेन लौटें
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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