C++ですべての適切な文字列を検索

文字列は、そのサイズがnで、アルファベット順にs1以上であり、アルファベット順にs2以下であり、サブストリングとして悪がない場合に、goodと呼ばれます。答えは非常に大きい可能性があるため、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

• サイズの配列dpを定義します：（N + 1）x（M + 1）x2。

• サイズの配列trを定義します：（M + 1）x26。

• m：=1 ^ 9 + 7

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（（a mod m）+（b mod m））mod m

• 関数solve（）を定義します。これには、n、s、e、

  が必要です。

• 配列を逆にするe

• trとdpを0で埋める

• 初期化i：=0の場合、i

  • f：=インデックス0からi-1までのeの部分文字列

  • 初期化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]）

• ret：=0

• 初期化i：=0の場合、i

  • ret：=add（ret、dp [0、i、1]）

• retを返す

• メインの方法から、次のようにします-

• ok：=1

• 初期化i：=0の場合、i

  • ok：=1（s1[i]が'a'のASCIIと同じ場合

• okでない場合はゼロ以外の場合、-

  • 初期化i：=s1のサイズの場合、i> =0の場合、更新（iを1つ減らす）、do-

    • s1[i]が'a'と等しくない場合、-

      • （s1 [i]を1減らします）

      • ループから出てきます

    • s1 [i]：='z'のASCII

• left：=（okがゼロ以外の場合は0、それ以外の場合はsolve（n、s1、evil））

• 右：=Solve（n、s2、evil）

• return（right-left + 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