Pythonで個別のサブシーケンスの数を見つけるプログラム

文字列sがあるとすると、文字列sの個別のサブシーケンスの数をカウントする必要があります。答えが大きすぎる場合は、10 ^ 9+7を法とする結果を返します。

したがって、入力がs ="bab"の場合、6つの異なるシーケンスがあり、これらは "a"、 "b、" ba "、" ab "、" bb "、" abb "であるため、出力は6になります。 。

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

• dp：=サイズがsと同じで、0で埋められた配列

• m：=10 ^ 9 + 7

• 各インデックスiとsのアイテム文字について、実行します

  • ind：=右からsのi番目の文字のインデックス

  • dp [i]：=1 +（dp [インデックス0からi-1まで]のすべての要素の合計）indが-1と同じ場合はmod mそれ以外の場合（インデックスindからi-1までのdp[のすべての要素の合計] ]）mod m

• dpmodmのすべての要素の合計を返す

例

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

def solve(s):
   dp, m = [0] * len(s), 10**9 + 7
   for i, char in enumerate(s):
      ind = s.rfind(char, 0, i)
      dp[i] = 1 + sum(dp[:i]) % m if ind == -1 else sum(dp[ind:i]) % m
   return sum(dp) % m

s = "bab"
print(solve(s))

入力

"abcd", "abcdbcd"

出力

6