Python에서 고유한 하위 시퀀스의 수를 찾는 프로그램

<시간/>

문자열 s가 있다고 가정하고 문자열 s의 고유한 하위 시퀀스 수를 계산해야 합니다. 답이 너무 크면 결과 모듈로 10^9 + 7을 반환합니다.

따라서 입력이 s ="bab"과 같으면 "a", "b, "ba", "ab", "bb", "abb"와 같은 6개의 다른 시퀀스가 있기 때문에 출력은 6이 됩니다. .

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

dp :=s와 크기가 같고 0으로 채워진 배열
m :=10^9 + 7
s의 각 인덱스 i 및 항목 char에 대해 수행
- ind :=오른쪽부터 s의 i번째 문자 인덱스
- dp[i] :=1 + (dp[인덱스 0에서 i-1까지]에 있는 모든 요소의 합) ind가 -1과 같으면 mod m 그렇지 않으면 (dp[인덱스 ind에서 i-1까지]에 있는 모든 요소의 합 ]) 모드 m
dp mod m
의 모든 요소의 합을 반환합니다.

예

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

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"