用 Python 编写程序，查找字符串及其子字符串的总相似度

pythonserver side programmingprogramming更新于 2025/12/13 2:20:17

假设我们有一个字符串 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。

为了解决这个问题，我们将遵循以下步骤 −

长度 := s 的大小
总计 := 长度
z := 最初包含 0 的列表
l := 0, r := 0
对于范围从 1 到长度 - 1 的 k，执行
- 如果 k > r，则
  - 匹配:= 0
  - 索引 := k
- 当索引 < length，do
  - 如果 s[index] 与 s[match] 相同，则
    - match := match + 1
    - index := index + 1
  - 否则，
    - 退出循环
- 在 z 末尾插入匹配项
- 如果匹配项 > 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
      - 否则，
        
        come out from loop
    - 在 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))