在python中找出字符串与其后缀之间的相似性的程序

Z时代
2024-01-10
分类：综合

假设，我们得到一个字符串“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.

示例

让我们看看以下实现以获得更好的理解 -

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'))