leetcode 2564. 子字符串异或查询[题解]

链接：子字符串异或查询
思路：题目说 \(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 ;
    }
};