计算Python中同构子串数量的程序

假设我们有一个字符串 s，我们必须找到 s 的同构子串的数量。答案可能非常大，所以返回模 10^9+7 的答案。当字符串的所有字符都相同时，就称该字符串是同质的。

因此，如果输入类似于 s = "xyyzzzzxx"，那么输出将是 13，因为同构子串的列表如下

• 1.“x”出现三次。

• “xx”出现一次。

• 3. “y”出现两次。

• “yy”出现一次。

• 5. “z”出现三次。

• “zz”出现两次。

• “zzz”出现一次。

所以，(3 + 1 + 2 + 1 + 3 + 2 + 1) = 13。

示例

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

def solve(s):
   s+="@"
   h={}
   prev=s[0]
   c=1
   for i in s[1:]:
      if prev!=i:
         if prev*c in h:
            h[prev*c]+=1
         else:
            h[prev*c]=1
         c=1
      if prev == i:
         c += 1
      prev = i
   fin=0
   for i in h:
      t=len(i)
      k=0
      while t!=0:
         k+=t
         t-=1
      fin+=k*h[i]
   return fin % 1000000007

s = "xyyzzzxx"
print(solve(s))

输入

"xyyzzzxx"

13