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

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

为了解决这个问题，我们将遵循以下步骤：

length := s的长度
total := length
z := 初始为空列表
l := 0, r := 0
对于k从1到length - 1，执行：
- 如果k > r，则
  - match:= 0
  - index := k
- 当index < length时，执行：
  - 如果s[index]与s[match]相同，则
    - match := match + 1
    - index := index + 1
  - 否则，
    - 退出循环
- 将match添加到z的末尾
- 如果match > 0，则
  - total := total + match
  - l := k
  - r := index-1
- 否则，
  - 如果z[k-l] < (r-k)+1，则
    - 将z[k-l]添加到z的末尾
    - total := total + z[k-l]
  - 否则，
    - match := r-k
    - index := r
    - 当index < length时，执行：
      - 如果s[index]与s[match]相同，则
        match := match + 1
        index := index + 1
      - 否则，
        退出循环
    - 将match添加到z的末尾
    - total := total + match
    - l := k
    - r := index-1
返回total

示例

让我们来看下面的实现，以便更好地理解：

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

输入

"pqpqpp"

输出

Arnab Chakraborty

更新于：2021年10月7日

278 次查看

开启你的职业生涯

完成课程获得认证

开始学习