查詢Python中最長的子字串，該子字串既是字首又是字尾，並且也出現在字串中

假設我們有一個給定的字串，我們需要找到最大的子字串，它是該給定字串的字首、字尾和子字串。如果沒有這樣的子字串，則返回-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(string)

  • n := 字串的大小

  • 如果long_pref_suff[n - 1]等於0，則

    • 返回-1

  • 對於範圍從0到n-1的i，執行以下操作：

    • 如果long_pref_suff[i]等於long_pref_suff[n - 1]，則

      • 返回string的子字串（從索引0到long_pref_suff[i]）

  • 如果long_pref_suff[long_pref_suff[n - 1] - 1]等於0，則

    • 返回-1

  • 否則，

    • 返回string的子字串（從索引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

更新於：2020年8月20日

809 次檢視

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告