Python 中查詢給定字串的所有迴文子字串 - 方法二

假設我們有一個字串；我們需要從該字串中找到所有迴文子字串。這裡 aa 和 aa 被認為是兩個子字串，而不是一個。

因此，如果輸入類似於 redivider，則輸出將為 ['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider', 'i', 'd', 'e', 'r']

為了解決這個問題，我們將遵循以下步驟 -

• v := 一個新的列表
• pos := 0.0
• 當 pos < s 的大小 時，執行
  • rad := pos - (pos 的整數部分)
  • 當 (pos + rad) < s 的大小 且 (pos - rad) >= 0 且 (s[pos - rad 的整數部分] 等於 s[pos + rad 的整數部分]) 時，執行
    • 將 s[從索引 pos - rad 的整數部分 到 pos + rad + 1 的整數部分] 插入到 v 的末尾
    • rad := rad + 1
  • pos := pos + 0.5
• 返回 v

示例程式碼

讓我們看看以下實現，以便更好地理解 -

 即時演示

def get_all_pal_sub(s):
   v = []
   pos = 0.0
   while pos < len(s):
      rad = pos - int(pos)
      while ((pos + rad) < len(s) and (pos - rad) >= 0 and (s[int(pos - rad)] == s[int(pos + rad)])):
         v.append(s[int(pos - rad): int(pos + rad + 1)])
         rad += 1
      pos += 0.5
   return v
v = get_all_pal_sub("redivider")
print(len(v))
print(v)

輸入

"redivider"

輸出

13 ['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider', 'i', 'd', 'e', 'r']

Arnab Chakraborty

更新於: 2020年8月28日

88 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習