Missing Test Case - 3006. Find Beautiful Indices in the Given Array I #19485
Description
LeetCode Username
tredsused70
Problem number, title, and link
- Find Beautiful Indices in the Given Array I https://leetcode.com/problems/find-beautiful-indices-in-the-given-array-i/
Category of the bug
- [.] Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
Description of the bug
Code that gets "Accepted" verdict when submitted, gets WA on some testcases when used "Run" operation.
Language used for code
C++
Code used for Submit/Run operation
typedef long long ll;
ll P[500001], p = 233;
ll mod = 1e9+7;
ll S[500001];
void init()
{
if(P[0]==1) return;
P[0] = 1;
for(int i=1;i<=500000;++i)
{
P[i] = (P[i-1] * p) % mod;
}
}
ll f(int a,int b)
{
if(a==0) return S[b];
ll ans = S[b] - S[a-1] * P[b-a+1];
ans %= mod;
ans += mod;
ans %= mod;
return ans;
}
ll Hash(string s)
{
ll ans = 0;
for(char c:s)
{
ans = (ans * p + c) % mod;
}
return ans;
}
class Solution {
public:
vector<int> beautifulIndices(string s, string a, string b, int k) {
init();
int n = s.size();
S[0] = s[0];
for(int i=1;i<n;++i)
{
S[i] = (S[i-1] * p + s[i]) % mod;
}
set<int> sta,stb;
int h = Hash(a);
int len = a.size();
for(int i=0;i+len-1<n;++i)
{
if(f(i,i+len-1)==h) sta.insert(i);
}
h = Hash(b);
len = b.size();
for(int i=0;i+len-1<n;++i)
{
if(f(i,i+len-1)==h) stb.insert(i);
}
// for(int x:sta) cout<<x<<" ";
// cout<<endl;
vector<int> ans;
for(int x:sta)
{
int t = x - k;
auto ite = stb.lower_bound(t);
if(ite == stb.end()) continue;
if(*ite <= x+k) ans.push_back(x);
}
return ans;
}
};
Expected behavior
When s = "awacab", a = "awacab", b = "maqafa", k = 4, hashes of strings a and b are equal in the code, which leads to WA when runned on this testcase. However the code gets "Accepted" verdict when submitted.
Screenshots
