数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中查找所有好字符串
假设我们有两个字符串s1和s2。这些字符串的大小为n，我们还有一个名为evil的字符串。我们必须找到好字符串的数量。
当字符串大小为n，按字母顺序大于或等于s1，按字母顺序小于或等于s2，并且没有evil作为子字符串时，该字符串被称为好字符串。答案可能非常大，因此返回答案模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的数组dp。
定义一个大小为：(M+1) x 26的数组tr。
m := 10^9 + 7
定义一个函数add()，它将接收a，b，
返回((a mod m) + (b mod m)) mod m
定义一个函数solve()，它将接收n，s，e，
反转数组e
用0填充tr和dp
对于初始化i := 0，当i < e的大小，更新（i递增1），执行：
f := e从索引0到i-1的子字符串
对于初始化j := 0，当j < 26，更新（j递增1），执行：
ns := f + (j + 'a'的ASCII码)
对于初始化k := i + 1，（k递减1），执行：
如果ns从索引(i + 1 - k)到结尾的子字符串与e从索引0到k-1的子字符串相同，则：
tr[i, j] := k
退出循环
m := e的大小
对于初始化i := 0，当i <= n，更新（i递增1），执行：
对于初始化j := 0，当j < m，更新（j递增1），执行：
dp[i, j, 0] := 0
dp[i, j, 1] := 0
dp[n, 0, 1] := 1
对于初始化i := n - 1，当i >= 0，更新（i递减1），执行：
对于初始化j := 0，当j < e的大小，更新（j递增1），执行：
对于初始化k := 0，当k < 26，更新（k递增1），执行：
对于l in range (0, 1)
如果k > s[i] - 'a'的ASCII码，则：
nl := 0
否则，如果k < s[i] - 'a'的ASCII码，则：
nl := 1
否则
nl := l
dp[i, tr[j, k], nl] := add(dp[i, tr[j, k], nl], dp[i + 1, j, l])
ret := 0
对于初始化i := 0，当i < e的大小，更新（i递增1），执行：
ret := add(ret, dp[0, i, 1])
返回ret
从主方法执行以下操作：
ok := 1
对于初始化i := 0，当i < s1的大小且ok非零，更新（i递增1），执行：
当s1[i]与'a'的ASCII码相同时，ok := 1
如果ok非零，则：
对于初始化i := s1的大小，当i >= 0，更新（i递减1），执行：
如果s1[i]不等于'a'，则：
(s1[i]递减1)
退出循环
s1[i] := 'z'的ASCII码
left := (如果ok非零，则0，否则solve(n, s1, evil))
right := solve(n, s2, evil)
返回(right - left + 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
382 次查看
