দুটি স্ট্রিং s1, s2 (দৈর্ঘ্য n) এবং evil স্ট্রিং দেওয়া আছে। কতগুলো "গুড" স্ট্রিং আছে? গুড স্ট্রিং: দৈর্ঘ্য n, s1 >= alphabetically >= s2, evil সাবস্ট্রিং হিসেবে নেই। মডুলো ১০^৯+৭।
উদাহরণ: n=2, s1="bb", s2="db", evil="a" -> ৫১। 'b' দিয়ে ২৫, 'c' দিয়ে ২৫, 'd' দিয়ে ১ (db) = ৫১।
সমাধানের ধাপসমূহ
- KMP অটোমেটন (tr[M+1][26]) বানান evil-র জন্য।
- DP[i][j][tight]: i পজিশন, j = evil-এ ম্যাচ করা প্রিফিক্স দৈর্ঘ্য, tight = s-এ বাউন্ডেড কিনা।
- বটম-আপ DP: dp[n][0][1] = 1। i=n-1 থেকে ০, সব j, k (অক্ষর), l (tight) için ট্রানজিশন।
- solve(n, s, evil): s-এ বাউন্ডেড স্ট্রিংগুলোর সংখ্যা।
- ফলাফল = solve(n, s2, evil) - solve(n, s1-1, evil) (মডুলো)।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int N = 500, 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_len = e.size();
for (int i = 0; i <= n; i++)
for (int j = 0; j < m_len; 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; }
else s1[i] = 'z';
}
int left = ok ? 0 : solve(n, s1, evil);
int right = solve(n, s2, evil);
return (right - left + m) % m;
}
};
int main() {
Solution ob;
cout << ob.findGoodStrings(2, "bb", "db", "a");
return 0;
}
ইনপুট
2, "bb", "db", "a"
আউটপুট
51
