用 Python 编写一个程序来计算同质子字符串的数量

pythonserver side programmingprogramming更新于 2025/11/30 21:32:17

假设我们有一个字符串 s，我们必须找出 s 中同质子字符串的数量。答案可能非常大，因此返回答案对 10^9+7 取模。当字符串的所有字符都相同时，该字符串被称为同质字符串。

因此，如果输入为 s = "xyyzzzxx"，则输出将为 13，因为同质子字符串的列表如下

1."x" 出现三次。
"xx" 出现一次。
3. "y" 出现两次。
"yy"出现一次。
5. "z"出现三次。
"zz"出现两次。
"zzz"出现一次。

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

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

s := s 连接"@"
h:= 一个新的映射
prev:= s[0]
c:= 1
对于 s 中从索引 1 到末尾的每个 i，执行
- 如果 prev 与 i 不同，则
  - 如果 prev*c 存在于 h 中，则
    - h[prev*c] := h[prev*c] + 1
  - 否则，
    - h[prev*c]:= 1
  - c:= 1
- 如果 prev 与 i 相同，则
  - c := c + 1
- prev := i
fin:= 0
对于 h 中的每个 i，执行
- t:= size of i
- k:= 0
- 当 t 不等于 0 时，执行
  - k := k + t
  - t := t - 1
- fin := fin + k*h[i]
返回 fin mod 10^9+7

示例

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

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