用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’ 相似度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
while 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'))