Missing Test Case - 3036. Number of Subarrays That Match a Pattern II #20266
Description
LeetCode Username
hrishavratan
Problem number, title, and link
3036. Number of Subarrays That Match a Pattern II
Category of the bug
- Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
Description of the bug
It expects 0 as answer for testcase when
nums =[110,105,98,99,98,97,98,97,96,95,94,94,93,92,91]
pattern =[0,0,-1,-1,-1,-1,1,0,-1,-1,-1,0,-1,0]
Language used for code
C++
Code used for Submit/Run operation
class Solution {
public:
vector<int> rabin_karp(string const& s, string const& t) {
const int p = 31;
const int m = 1e9 + 21;
int S = s.size(), T = t.size();
vector<long long> p_pow(max(S, T));
p_pow[0] = 1;
for (int i = 1; i < (int)p_pow.size(); i++)
p_pow[i] = (p_pow[i-1] * p) % m;
vector<long long> h(T + 1, 0);
for (int i = 0; i < T; i++)
h[i+1] = (h[i] + (t[i] - 'a' + 1) * p_pow[i]) % m;
long long h_s = 0;
for (int i = 0; i < S; i++)
h_s = (h_s + (s[i] - 'a' + 1) * p_pow[i]) % m;
vector<int> occurrences;
for (int i = 0; i + S - 1 < T; i++) {
long long cur_h = (h[i+S] + m - h[i]) % m;
if (cur_h == h_s * p_pow[i] % m)
occurrences.push_back(i);
}
return occurrences;
}
int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
int n = nums.size(), m = pattern.size();
vector<int> v(n - 1);
string s;
for (int i = 0; i < n - 1; i++) {
if (nums[i] < nums[i+1]) v[i] = 1;
else if (nums[i] > nums[i+1]) v[i] = -1;
s += v[i] + 'b';
}
string t;
for (int x : pattern) t += char(x + 'b');
return size(rabin_karp(t, s));
}
};
Expected behavior
0