在 Python 中查找字符串及其子字符串的总相似度的程序

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

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

示例

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

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