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

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

तो, यदि इनपुट "languagepythonlanguageinterestinglanguage" जैसा है, तो आउटपुट "language" होगा।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

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

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

• long_pref_suff := आकार n का एक ऐरे, और 0 से भरा हुआ

• size := 0, long_pref_suff[0] := 0, i := 1

• जब i < n शून्येतर है, करें:

  • यदि string[i], string[size] के समान है, तो:

    • size := size + 1

    • long_pref_suff[i] := size

    • i := i + 1

  • अन्यथा,

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

      • size := long_pref_suff[size - 1]

    • अन्यथा,

      • long_pref_suff[i] := 0

      • i := i + 1

• long_pref_suff लौटाएं

• मुख्य विधि से, निम्नलिखित करें:

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

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

• यदि long_pref_suff[n-1], 0 के समान है, तो:

  • -1 लौटाएं

• i को 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