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：=长度
z：=包含0的列表
l：= 0，r：= 0
对于范围为1到length-1的k，
- 如果k> r，则
  - match：= 0
  - index：= k
- 当index<length时，
  - 如果s [index]与s [match]相同，则
  - match：= match + 1
  - index：= index+1
  - 否则，
  - 跳出循环
- 在z的末尾插入匹配
- 如果match> 0，则
  - total：= total + match
  - l：= k
  - r：= index-1
- 否则，
  - 如果z [k-l] <（r-k）+ 1，则
  - 在z的末尾插入z [k-l]
  - total：= total + z [k-l]
  - 否则，
  - match：= r-k
  - index：= r
  - 当index<length时，
    - 如果s [index]与s [match]相同，则
    - match：= match + 1
    - index：= index+1
    - 否则，
    - 跳出循环
  - 在z的末尾插入匹配
  - total：= total+match
  - l：= k
  - r：= index-1
返回总和

示例

让我们看一下以下实现代码以获得更好的理解−

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