题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
typedef pair<int,int> PII;
class Solution {
public:
vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& q) {
unordered_map<long long,PII> mp;
int n=s.size();
for(int i=0;i<n;i++)
{
long long t=0;
for(int j=i;j<min(n,i+40);j++)
{
if(s[j]=='0') t=t*2+0;
else t=t*2+1;
if(!mp.count(t)){
mp[t]={i,j};
}
else
{
int left=mp[t].first,right=mp[t].second;
if(right-left+1>j-i+1||(right-left+1==j-i+1&&i<left)){
mp[t]={i,j};
}
}
}
}
vector<vector<int>> res;
for(int i=0;i<q.size();i++){
long long t=q[i][0]^q[i][1];
if(mp.count(t)){
res.push_back({mp[t].first,mp[t].second});
}
else res.push_back({-1,-1});
}
return res;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla