用 Python 编写程序，找出字符串与其后缀之间的相似性

pythonserver side programmingprogramming更新于 2025/12/18 16:44:17

假设，我们给定一个字符串"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' 相似度 5
'potp' 相似度 0
'otp'相似度 0
'tp' 相似度 2
'p' 相似度 0

相似度总和 = 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 末尾插入 return_list[i-q]
    - i := i + 1
    - r := 0
- 否则，
  - 当 (i + r < input_str 的大小) 且 (input_str[r] 与 input_str[i+r] 相同) 时，执行
    - r := r + 1
  - 在 return_list 末尾插入 r
  - 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'))