सबसे लंबी उप-स्ट्रिंग खोजें जो उपसर्ग, प्रत्यय है और पायथन में स्ट्रिंग के अंदर भी मौजूद है

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

इसलिए, यदि इनपुट "भाषापायथनभाषादिलचस्प भाषा" जैसा है, तो आउटपुट "भाषा" होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें get_lps() । यह स्ट्रिंग लेगा

• n :=स्ट्रिंग का आकार

• long_pref_suff :=आकार n की एक सरणी, और 0 से भरें

• आकार :=0, long_pref_suff[0] :=0, i :=1

• जबकि i

  • यदि स्ट्रिंग [i] स्ट्रिंग [आकार] के समान है, तो

    • आकार :=आकार + 1

    • long_pref_suff[i] :=आकार

    • मैं :=मैं + 1

  • अन्यथा,

    • यदि आकार 0 के समान नहीं है, तो

      • आकार :=long_pref_suff[size - 1]

    • अन्यथा,

      • long_pref_suff[i] :=0

      • मैं :=मैं + 1

• long_pref_suff लौटाएं

• मुख्य विधि से, निम्न कार्य करें -

• long_pref_suff :=get_lps(स्ट्रिंग)

• n :=स्ट्रिंग का आकार

• अगर long_pref_suff[n - 1] 0 के समान है, तो

  • वापसी -1

• मैं के लिए 0 से n -1 की सीमा में, करो

  • अगर long_pref_suff[i] long_pref_suff[n - 1] के समान है, तो

    • स्ट्रिंग की वापसी सबस्ट्रिंग [इंडेक्स 0 से long_pref_suff[i]]

• अगर long_pref_suff[long_pref_suff[n - 1] - 1] 0 के समान है, तो

  • वापसी -1

• अन्यथा,

  • स्ट्रिंग का रिटर्न सबस्ट्रिंग [इंडेक्स 0 से long_pref_suff [long_pref_suff[n - 1] - 1]]

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

def get_lps(string):
   n = len(string)
   long_pref_suff = [0 for i in range(n)]
   size = 0
   long_pref_suff[0] = 0
   i = 1
   while (i < n):
      if (string[i] == string[size]):
         size += 1
         long_pref_suff[i] = size
         i += 1
      else:
         if (size != 0):
            size = long_pref_suff[size - 1]
         else:
            long_pref_suff[i] = 0
            i += 1
   return long_pref_suff
def get_longest_substr(string):
   long_pref_suff = get_lps(string)
   n = len(string)
   if (long_pref_suff[n - 1] == 0):
      return -1
   for i in range(0,n - 1):
      if (long_pref_suff[i] == long_pref_suff[n - 1]):
         return string[0:long_pref_suff[i]]
      if (long_pref_suff[long_pref_suff[n - 1] - 1] == 0):
         return -1
      else:
         return string[0:long_pref_suff[long_pref_suff[n - 1] - 1]]

string = "languagepythonlanguageinterestinglanguage"
print(get_longest_substr(string))

इनपुट

"languagepythonlanguageinterestinglanguage"

आउटपुट

language