在C ++中查找所有好的字符串

假设我们有两个字符串s1和s2。这些字符串的大小为n，我们还有另一个字符串称为evil。我们必须找到好字符串的数量。

如果字符串的大小为n，则按字母顺序大于或等于s1，按字母顺序小于或等于s2，并且作为子字符串不包含邪恶，则该字符串称为良。答案可能非常大，因此请以10 ^ 9 + 7为模返回答案。

因此，如果输入类似于n = 2，则s1 =“ bb”，s2 =“ db”，evil =“ a”，则输出将为51，因为有25个以b开头的良好字符串。“ bb”，“ bc”，“ bd”，...“ bz”，那么有25个以“ cb”，“ cc”，“ cd”，...，“ cz”开头的好字符串带有d的字符串是“ db”。

为了解决这个问题，我们将遵循以下步骤-

• N：= 500，M：= 50

• 定义大小为（N + 1）x（M + 1）x 2。

• 定义大小为（M + 1）x 26的数组tr。

• m：= 1 ^ 9 + 7

• 定义一个函数add()，这将花费a，b，

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

• 定义一个函数solve()，它将花费n，s，e，

• 反转数组e

• 用0填充tr和dp

• 对于初始化i：= 0，当i <e的大小时，更新（将i增加1），执行-

• ns：= f +（j +'a'的ASCII）

• 对于初始化k：= i + 1，（将k减1），-

• tr [i，j]：= k

• 从循环中出来

• 如果从索引（i +1-k）到结尾的ns子字符串与从索引0到e的k-1的e子字符串相同，则-

• f：= e从索引0到i-1的子字符串

• 对于初始化j：= 0，当j <26时，更新（将j增加1），执行-

list-paddingleft-2" style="list-style-type: square;">

• m：= e的大小

• 对于初始化i：= 0，当i <= n时，更新（将i增加1），请执行-

• dp [i，j，0]：= 0

• dp [i，j，1]：= 0

• 对于初始化j：= 0，当j <m时，更新（将j增加1），执行-

• dp [n，0，1]：= 1

• 对于初始化i：= n-1，当i> = 0时，更新（将i减1），-

• 对于初始化k：= 0，当k <26时，更新（k增加1），-

• 如果k> s [i]-'a'的ASCII，则-

• 否则，当k <s [i]-'a'的ASCII时，则-

• 除此以外

• dp [i，tr [j，k]，nl]：= add（dp [i，tr [j，k]，nl]，dp [i + 1，j，l]）

• nl：= 0

• nl：= 1

• nl：= l

• 适用于范围(0,1)中的l

• 对于初始化j：= 0，当j <e的大小时，更新（将j增加1），执行-

• ret：= 0

• 对于初始化i：= 0，当i <e的大小时，更新（将i增加1），执行-

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

• 返回ret

• 从主要方法中执行以下操作-

• 好的：= 1

• 对于初始化i：= 0，当i <s1的大小且ok不为零时，更新（将i增加1），执行-

• ok：= 1，当s1 [i]与'a'的ASCII相同

• 如果不能，则为非零，则-

• 如果s1 [i]不等于'a'，则-

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

• （将s1 [i]减1）

• 从循环中出来

• 对于初始化i：= s1的大小，当i> = 0时，更新（将i减1），执行-

• 左：=（如果ok为非零，则为0，否则为solve（n，s1，邪恶））

• 对：= solve(n,s2,evil)

• 返回（右-左+ 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));
      memhtml" target="_blank">set(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