假设我们有两个字符串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