C++에서 문자열의 고유한 하위 시퀀스 수를 계산하는 프로그램

<시간/>

문자열 s가 있다고 가정하고 s의 비어 있지 않은 고유 하위 시퀀스의 수를 찾아야 합니다. 답이 매우 크면 결과를 10^9 + 7로 수정합니다.

따라서 입력이 s ="xxy"와 같으면 "x", "xx", "xy", "y" 및 "xxy"라는 5개의 하위 시퀀스가 있으므로 출력은 5가 됩니다.

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

m :=10^9 + 7
n :=s
의 크기
크기가 26인 배열 테이블 정의
해상도 :=0
for initialize i :=1, i <=n일 때 업데이트(i를 1만큼 증가), do−
- c :=s[i − 1] − 'a'의 ASCII
- curr :=(res + 1 − table[c] + m) mod m
- res :=(res + curr) 모드 m
- table[c] :=(table[c] + curr) 모드 m
반환 해상도

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
int solve(string s) {
   int n = s.size();
   vector<int> table(26);
   long long res = 0;
   for (int i = 1; i <= n; ++i) {
      int c = s[i − 1] − 'a';
      int curr = (res + 1 − table[c] + m) % m;
      res = (res + curr) % m;
      table[c] = (table[c] + curr) % m;
   }
   return res;
}
int main(){
   string s = "xxy";
   cout << solve(s);
}

입력

"xxy"