在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),执行-

    • 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));
              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