C++에서 모든 좋은 문자열 찾기

두 개의 문자열 s1과 s2가 있다고 가정합니다. 이 문자열의 크기는 n이고, 악이라는 또 다른 문자열도 있습니다. 좋은 문자열의 수를 찾아야 합니다.

문자열은 크기가 n이고 알파벳순으로 s1보다 크거나 같으며 알파벳순으로 s2보다 작거나 같으며 하위 문자열로 악이 없을 때 좋음이라고 합니다. 답은 매우 클 수 있으므로 모듈로 10^9 + 7을 반환합니다.

따라서 입력이 n =2, s1 ="bb", s2 ="db", evil ="a"인 경우 b로 시작하는 25개의 좋은 문자열이 있으므로 출력은 51이 됩니다. "bb", "bc", "bd", ... "bz", "cb", "cc", "cd",...,"cz"로 시작하는 25개의 좋은 문자열과 다른 좋은 문자열이 있습니다. d가 있는 문자열은 "db"입니다.

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

N :=500, M :=50
(N+1) x (M+1) x 2 크기의 배열 dp를 정의합니다.
(M+1) x 26 크기의 배열 tr을 정의합니다.
m :=1^9 + 7
add() 함수를 정의하면, b,
return ((a mod m) + (b mod m)) mod m
solve() 함수를 정의하면 n, s, e,
가 필요합니다.
배열 e
반전
tr 및 dp를 0으로 채우기
initialize i :=0의 경우 i
- f :=인덱스 0에서 i까지의 e의 부분 문자열 - 1
- initialize j :=0의 경우 j <26일 때 업데이트(j를 1만큼 증가), 수행 -
  - ns :=f + (j + 'a'의 ASCII)
  - k를 초기화하려면 :=i + 1, (k를 1만큼 감소) −
    - 인덱스(i + 1 - k)에서 끝까지 ns의 부분 문자열이 인덱스 0에서 e의 k-1까지 e의 부분 문자열과 같으면 -
      - tr[i, j] :=k
      - 루프에서 나오세요
m :=e의 크기
i:=0 초기화의 경우, i <=n일 때 업데이트(i를 1만큼 증가), -
수행
- j 초기화의 경우:=0, j
  - dp[i, j, 0] :=0
  - dp[i, j, 1] :=0
dp[n, 0, 1] :=1
초기화 i :=n - 1의 경우, i>=0일 때 업데이트(i를 1만큼 감소), −
- j 초기화의 경우 :=0, j
  - 초기화 k :=0의 경우 k <26일 때 업데이트(k를 1만큼 증가), −
    - 범위 (0, 1)의 l에 대해
      - k> s[i] - 'a'의 ASCII이면 -
        
        nl :=0
      - 그렇지 않으면 k
        
        nl :=1
      - 그렇지 않으면
        
        nl :=l
      - dp[i, tr[j, k], nl] :=add(dp[i, tr[j, k], nl], dp[i + 1, j, l])
렛 :=0
initialize i :=0의 경우 i
- ret :=add(ret, dp[0, i, 1])
리턴 렛
주요 방법에서 다음을 수행하십시오 -
확인 :=1
initialize i :=0의 경우, i 를 수행합니다.
- ok :=s1[i]가 'a'의 ASCII와 같을 때 1
ok가 아닌 경우 0이 아닌 경우 -
- for initialize i :=s1의 크기, i>=0일 때 업데이트(i 1만큼 감소), do-
  - s1[i]가 'a'와 같지 않으면 -
    - (s1[i]를 1만큼 감소)
    - 루프에서 나오세요
  - s1[i] :='z'의 ASCII
left :=(ok가 0이 아니면 0, 그렇지 않으면 solve(n, s1, evil))
오른쪽 :=해결(n, s2, 악)
리턴(오른쪽 - 왼쪽 + m) 모드 m

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

예시

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int N = 500;
const int M = 50;
int dp[N + 1][M + 1][2];
int tr[M + 1][26];
const lli m = 1e9 + 7;
class Solution {
   public:
   int add(lli a, lli b){
      return ((a % m) + (b % m)) % m;
   }
   lli solve(int n, string s, string e){
      reverse(e.begin(), e.end());
      memset(tr, 0, sizeof(tr));
      memset(dp, 0, sizeof(dp));
      for (int i = 0; i < e.size(); i++) {
         string f = e.substr(0, i);
         for (int j = 0; j < 26; j++) {
            string ns = f + (char)(j + 'a');
            for (int k = i + 1;; k--) {
               if (ns.substr(i + 1 - k) == e.substr(0, k)) {
                  tr[i][j] = k;
                  break;
               }
            }
         }
      }
      int m = e.size();
      for (int i = 0; i <= n; i++) {
         for (int j = 0; j < m; j++) {
            dp[i][j][0] = dp[i][j][1] = 0;
         }
      }
      dp[n][0][1] = 1;
      for (int i = n - 1; i >= 0; i--) {
         for (int j = 0; j < e.size(); j++) {
            for (int k = 0; k < 26; k++) {
               for (int l : { 0, 1 }) {
                  int nl;
                  if (k > s[i] - 'a') {
                     nl = 0;
                  }
                  else if (k < s[i] - 'a') {
                     nl = 1;
                  }
                  else
                  nl = l;
                  dp[i][tr[j][k]][nl] = add(dp[i][tr[j][k]]
                  [nl], dp[i + 1][j][l]);
               }
            }
         }
      }
      lli ret = 0;
      for (int i = 0; i < e.size(); i++) {
         ret = add(ret, dp[0][i][1]);
      }
      return ret;
   }
   int findGoodStrings(int n, string s1, string s2, string evil) {
      bool ok = 1;
      for (int i = 0; i < s1.size() && ok; i++) {
         ok = s1[i] == 'a';
      }
      if (!ok) {
         for (int i = s1.size() - 1; i >= 0; i--) {
            if (s1[i] != 'a') {
               s1[i]--;
               break;
            }
            s1[i] = 'z';
         }
      }
      int left = ok ? 0 : solve(n, s1, evil);
      int right = solve(n, s2, evil);
      return (right - left + m) % m;
   }
};
main(){
   Solution ob;
   cout << (ob.findGoodStrings(2, "bb", "db", "a"));
}

입력

2, "bb", "db", "a"