Pythonの文字列のすべての部分文字列の個別の文字数をカウントするプログラム

小文字の文字列sがあるとすると、sのすべての部分文字列で異なる文字数の合計を見つける必要があります。答えが非常に大きい場合は、結果mod 10 ^ 9+7を返します。

したがって、入力がs ="xxy"のような場合、サブストリングとそのカウントは-

• "x"：1

• "x"：1

• 「y」：1

• "xx"：0（ "x"は区別されないため）

• 「xy」：2

• "xxy"：1（ "" x "は区別されないため）

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

• m：=10 ^ 9 + 7

• prev_seen：=新しい空のマップ

• ans：=0

• 関数util（）を定義します。これはi、シンボルを取ります

• prev_seen [symbol]：=単一の値が-1のリスト

• prev：=prev_seen [symbol]

• 前の最後にiを挿入

• 前のサイズが2より大きい場合、

  • left：=prevの最初の要素で、prevから最初の要素を削除します

  • 中央：=prev [0]、右：=prev [1]

  • cnt：=（中央-左）*（右-中央）

  • ans：=（ans + cnt）mod m

• インデックスiとsの値記号ごとに、実行します

  • util（i、シンボル）

• prev_seenの各シンボルについて、実行します

  • util（sのサイズ、シンボル）

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, s):
      m = 10 ** 9 + 7
      prev_seen = {}
      ans = 0
      def util(i, symbol):
         nonlocal ans
         prev = prev_seen.setdefault(symbol, [−1])
         prev.append(i)
         if len(prev) > 2:
            left = prev.pop(0)
            middle, right = prev
            cnt = (middle − left) * (right − middle)
            ans = (ans + cnt) % m
      for i, symbol in enumerate(s):
         util(i, symbol)
      for symbol in prev_seen:
         util(len(s), symbol)
      return ans
ob = Solution()
s = "xxy"
print(ob.solve(s))

入力

xxy

出力

6