Pythonで同種の部分文字列の数をカウントするプログラム

文字列sがあるとすると、sの同種の部分文字列の数を見つける必要があります。答えは非常に大きい可能性があるため、10 ^ 9+7を法として答えを返します。文字列のすべての文字が同じである場合、文字列は同種であると言われます。

したがって、入力がs ="xyyzzzxx"のようである場合、同種の部分文字列は

• 1.「x」が3回表示されます。

• 「xx」は1回表示されます。

• 3.「y」が2回表示されます。

• 「yy」は1回表示されます。

• 5.「z」は3回表示されます。

• 「zz」は2回表示されます。

• 「zzz」は1回表示されます。

したがって、（3 + 1 + 2 + 1 + 3 + 2 + 1）=13。

これを解決するには、次の手順に従います-

• s：=s連結"@"

• h：=新しい地図

• prev：=s [0]

• c：=1

• インデックス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

  • 前：=i

• fin：=0

• hの各iについて、実行します

  • t：=iのサイズ

  • k：=0

  • tは0と同じではありませんが、実行してください

    • k：=k + t

    • t：=t-1

  • fin：=fin + k * h [i]

• フィンmod10^ 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))

入力

"xyyzzzxx"

出力

13