Tìm tất cả các chuỗi tốt trong C ++

Giả sử chúng ta có hai chuỗi s1 và s2. Kích thước của các chuỗi này là n, và chúng ta cũng có một chuỗi khác được gọi là ác. Chúng ta phải tìm số lượng chuỗi tốt.

Một chuỗi được gọi là tốt khi kích thước của nó là n, nó lớn hơn hoặc bằng s1 theo thứ tự bảng chữ cái, nó nhỏ hơn hoặc bằng s2 theo thứ tự bảng chữ cái và nó không có ác nào là chuỗi con. Câu trả lời có thể rất lớn, vì vậy hãy trả về mô-đun câu trả lời 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là n =2, s1 ="bb", s2 ="db", evil ="a", thì đầu ra sẽ là 51, vì có 25 chuỗi tốt bắt đầu bằng b. "bb", "bc", "bd", ... "bz", sau đó có 25 chuỗi tốt bắt đầu bằng "cb", "cc", "cd", ..., "cz" và một chuỗi tốt khác chuỗi với d là "db".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• N:=500, M:=50

• Xác định một mảng dp có kích thước:(N + 1) x (M + 1) x 2.

• Xác định một mảng tr có kích thước:(M + 1) x 26.

• m:=1 ^ 9 + 7

• Xác định một hàm add (), điều này sẽ lấy a, b,

• return ((a mod m) + (b mod m)) mod m

• Xác định một hàm giải quyết (), điều này sẽ nhận n, s, e,

• đảo ngược mảng e

• Điền tr và dp bằng 0

• để khởi tạo i:=0, khi i

  • f:=chuỗi con của e từ chỉ số 0 đến i - 1

  • để khởi tạo j:=0, khi j <26, cập nhật (tăng j lên 1), thực hiện -

    • ns:=f + (j + ASCII của 'a')

    • để khởi tạo k:=i + 1, (giảm k đi 1), thực hiện -

      • nếu chuỗi con của ns từ chỉ mục (i + 1 - k) đến cuối giống với chuỗi con của ef từ chỉ số 0 đến k-1 của e, thì -

        • tr [i, j]:=k

        • Ra khỏi vòng lặp

• m:=kích thước của e

• để khởi tạo i:=0, khi i <=n, cập nhật (tăng i lên 1), thực hiện -

  • để khởi tạo j:=0, khi j

    • dp [i, j, 0]:=0

    • dp [i, j, 1]:=0

• dp [n, 0, 1]:=1

• để khởi tạo i:=n - 1, khi i> =0, cập nhật (giảm i đi 1), thực hiện -

  • để khởi tạo j:=0, khi j

    • để khởi tạo k:=0, khi k <26, hãy cập nhật (tăng k lên 1), thực hiện -

      • cho l trong phạm vi (0, 1)

        • nếu k> s [i] - ASCII của 'a', thì -

          • nl:=0

        • ngược lại khi k

          • nl:=1

        • Nếu không

          • nl:=l

        • dp [i, tr [j, k], nl]:=add (dp [i, tr [j, k], nl], dp [i + 1, j, l])

• ret:=0

• để khởi tạo i:=0, khi i

  • ret:=add (ret, dp [0, i, 1])

• trả lại ret

• Từ phương thức chính, thực hiện như sau -

• được rồi:=1

• để khởi tạo i:=0, khi i

  • ok:=1 khi s1 [i] giống với ASCII của 'a'

• nếu không ok là khác 0, thì -

  • để khởi tạo i:=size của s1, khi i> =0, hãy cập nhật (giảm i đi 1), do−

    • nếu s1 [i] không bằng 'a' thì -

      • (giảm s1 [i] đi 1)

      • Ra khỏi vòng lặp

    • s1 [i]:=ASCII của 'z'

• left:=(nếu ok là khác 0 thì 0, ngược lại thì giải (n, s1, evil))

• phải:=giải quyết (n, s2, ác)

• return (phải - trái + m) mod 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"

51