在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' 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'))输入
'tpotp'输出结果
5