資料結構
網路
關係資料庫管理系統 (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 次檢視
