Python程式：查詢字串及其子串的總相似度

假設我們有一個字串s。我們需要找到字串s與其每個字尾的相似度之和。這裡兩個字串之間的相似度是指兩者公共最長字首的長度。

例如，如果輸入是s = "pqpqpp"，則輸出將是11，因為該字串的字尾是"pqpqpp"、"qpqpp"、"pqpp"、"qpp"、"pp"和"p"。這些子串與字串"pqpqpp"的相似度分別為6、0、3、0、1和1。因此，總和是6 + 0 + 3 + 0 + 1 + 1 = 11。

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

  • length := s的長度
  • total := length
  • z := 初始為空列表
  • l := 0, r := 0
  • 對於k從1到length - 1，執行：
    • 如果k > r，則
      • match:= 0
      • index := k
    • 當index < length時，執行：
      • 如果s[index]與s[match]相同，則
        • match := match + 1
        • index := index + 1
      • 否則，
        • 退出迴圈
    • 將match新增到z的末尾
    • 如果match > 0，則
      • total := total + match
      • l := k
      • r := index-1
    • 否則，
      • 如果z[k-l] < (r-k)+1，則
        • 將z[k-l]新增到z的末尾
        • total := total + z[k-l]
      • 否則，
        • match := r-k
        • index := r
        • 當index < length時，執行：
          • 如果s[index]與s[match]相同，則
            • match := match + 1
            • index := index + 1
          • 否則，
            • 退出迴圈
        • 將match新增到z的末尾
        • total := total + match
        • l := k
        • r := index-1
  • 返回total

示例

讓我們來看下面的實現，以便更好地理解：

def solve(s):
   length = len(s)
   total = length

   z = [0]
   l = 0
   r = 0

   for k in range(1,length):
      if k > r:
         match=0
         index = k
         while index < length:
            if s[index] == s[match]:
               match +=1
               index +=1
            else:
               break
         z.append(match)
         if match > 0:
            total+=match
            l = k
            r = index-1
      else:
         if z[k-l] < (r-k)+1:
            z.append(z[k-l])
            total+=z[k-l]
         else:
            match = r-k
            index = r
            while index < length:
               if s[index] == s[match]:
                  match +=1
                  index +=1
               else:
                  break
            z.append(match)
            total+=match
            l = k
            r = index-1
   return total

s = "pqpqpp"
print(solve(s))

輸入

"pqpqpp"

輸出

11

更新於：2021年10月7日

278 次檢視

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告