在C ++中查找所有好的字符串
如果字符串的大小为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）x2。
定义大小为（M+1）x26的数组tr。
m：=1^9+7
定义一个函数add()，这将花费a，b，
return（（amodm）+（bmodm））modm
定义一个函数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）modm
让我们看下面的实现以更好地理解-
示例
#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