leetcode2564.子字符串异或查询[题解]xiaodangao

链接：子字符串异或查询
思路：题目说 $val \oplus first=second$

可得 $val = second \oplus first$

题目变成从 $0-1$ 串中找到最先出现的 $val$ 的二进制表示，注意是 $10^5$ 次询问。原来认为是 $AC$ 自动机类的东西，但仔细一想，数字最多 $30$ 位，那么字符串 $s$ 存在的数字数量仅为 $10^5$ 级别，那么我们可以预处理出所有数字的所在位置。

$Code$

class Solution {
public:
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
        #define ll int 
        map<ll,pair<int,int > >S;
        int sz = s.size() - 1;
        for(int len=1;len<=30;++len){
            for(int i=0;;++i){
                if(s[i] == '0' and len != 1)continue;
                if(i+len-1>sz)break;
                ll now = 0;
                for(int j=i;j<=i+len-1;++j){
                    now <<= 1;
                    if(s[j] == '1')now += 1ll;
                }
                if(S.count(now))continue;
                S[now] = {i,i+len-1};
            }
        }
        vector<vector<int> > ans;
        int tot = -1;
        for(auto i:queries){
            ll res = (ll)i[0] ^ i[1];
            if(S.count(res)){
                ans.push_back({S[res].first,S[res].second});
            }else {
                ans.push_back({-1,-1});
            }
        }
        return ans ;
    }
};

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。