在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

        以上是 在C ++中查找所有好的字符串 的全部内容, 来源链接: utcz.com/z/361360.html

        回到顶部