Python 程式：查詢字串與其後綴之間的相似度

假設我們給定一個字串 'input_str'。如果我們確定 'input_str' 中的所有後綴；例如，如果字串是 'abcd'，則字尾為 'abc'、'bcd'、'cd'、'd'。現在，我們透過 'input_str' 和字尾中最長公共字首的長度來檢查 'input_str' 和所有後綴之間的相似度。需要返回 'input_str' 和所有後綴之間相似度的總和。

因此，如果輸入類似於 input_str = 'tpotp'，則輸出將為 7

字串 'tpotp' 的所有後綴為 'tpotp'、'potp'、'otp'、'tp' 和 'p'。

如果我們檢查所有後綴與 input_str 的相似度，則得到 -

'tpotp' similarity 5
'potp' similarity 0
'otp' similarity 0
'tp' similarity 2
'p' similarity 0

Sum of similarities = 5 + 0 + 0 + 2 + 0 = 7.

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

  • return_list := 一個包含 input_str 大小的新列表
  • i := 1
  • p := 0
  • q := 0
  • r := 0
  • 當 i < input_str 的大小 時，執行
    • 如果 q < i < (q+p)，則
      • 如果 return_list[i-q] >= q+p-i，則
        • r := q + p - i
        • p := 0
        • q := 0
      • 否則，
        • 將 return_list[i-q] 插入到 return_list 的末尾
        • i := i + 1
        • r := 0
    • 否則，
      • 當 (i + r < input_str 的大小) 且 (input_str[r] 與 input_str[i+r] 相同) 時，執行
        • r := r + 1
      • 將 r 插入到 return_list 的末尾
      • p := r
      • q := i
      • i := i + 1
      • r := 0
  • 返回 return_list 中元素的總和

示例

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

def solve(input_str):
   return_list = [len(input_str)]
   i = 1
   p, q = 0,0
   r = 0
   while i < len(input_str):
      if q < i < (q+p):
         if return_list[i-q] >= q+p-i:
            r = q + p - i
            p, q = 0, 0
         else:
            return_list.append(return_list[i-q])
            i += 1
            r = 0
      else:
         while i + r < len(input_str) and input_str[r] == input_str[i+r]:
            r += 1
         return_list.append(r)
         p,q = r,i
         i += 1
         r = 0
      return sum(return_list)

print(solve('tpotp'))

輸入

'tpotp'

輸出

5

更新於: 2021-10-11

119 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告