P16640 Scrambled Words

· · 题解

我居然会做？\ 提供一个自己想到的 \mathcal O(TN\sqrt{10^5}) 的大常数哈希做法。

看到时间限制就知道这道题貌似非同一般。\ 考虑哈希。\ 如何哈希呢？\ 应该是分成三部分，开头字母，结尾字母，中间字符串。\ 对于中间字符串而言，只要所有字母出现次数一样，那么我们就认为中间字符串相等。\ 这样的话就可以给每个字母赋一个随机权值再求前缀和，以区间和作为这一段字符串的哈希值，只要哈希值相等那么字符串就相等。\ 对于首字母，上面的做法提醒我们还是可以给每个字母赋一个随机权值，以这个权值作为哈希值，尾字母同理。\ 接下来的问题就是怎么把这三个哈希值合成一个（虽然好像不合也可以但是不想看了）。\ 其实随便用什么运算把它们合在一起就行，比如异或。\ 当然，如果你用异或的话，对于同一个字母，它作为首字母的随机权值和它作为尾字母的随机权值必须不同，否则就没法分辨这个字母到底是首字母还是尾字母。

接下来考虑匹配。\ 首先我们可以先把原串有用的哈希值存下来然后对于每一个字符串匹配就行了。\ 因为字典中所有单词的长度之和不超过 10^5，所以单词的长度的种类是 \sqrt{10^5} 级别的。\ 大概讲一下就是等差数列求和，\sum_{i=1}^{n} i 的和是 n^2 级别的。\ 所以说我们只需要把有用的长度找出来就行了。\ 于是就有了这一份代码： ::::info[代码]

#include <bits/stdc++.h>
using namespace std;
mt19937 gen(time(0)^78623473);
#define ll long long
#define modd 998244353
int T,L,n,A,B,C,D,x[1000005];
int ans,lsh[20005],m,qz1[26],qz2[26],qz3[26];
ll H[1000005];
unordered_map<ll,bool>mp[450];
string t[20005];
char s[1000005];
void read(){
    cin >> L;
    for(int i = 1;i <= L;++i) cin >> t[i];
    for(int i = 1;i <= L;++i) t[i] = " " + t[i];
    cin >> s[1] >> s[2] >> n >> A >> B >> C >> D;
    const int mod = D;
    x[1] = s[1],x[2] = s[2],ans = 0;
    for(int i = 3;i <= n;++i) x[i] = ((ll)A * (ll)x[i-1] % mod + (ll)B * (ll)x[i-2] % mod + (ll)C) % mod;
    for(int i = 3;i <= n;++i) s[i] = (97 + x[i] % 26);
}
int get(const int X){
    int l = 1,r = m,mid;
    while(l < r){
        mid = ((l+r)>>1);
        if(X == lsh[mid]) return mid;
        else if(X > lsh[mid]) l = mid+1;
        else r = mid-1;
    }
    return l;//impossible
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> T;
    for(int iii = 1;iii <= T;++iii){
        read();
        for(int i = 0;i <= 25;++i) qz1[i] = gen() % modd,qz2[i] = gen() % modd,qz3[i] = gen() % modd;
        for(int i = 1;i <= L;++i) lsh[i] = (int)t[i].length()-1;
        sort(lsh+1,lsh+L+1),m = unique(lsh+1,lsh+L+1) - lsh - 1;
        for(int i = 1;i <= n;++i) H[i] = H[i-1] + qz1[s[i]-'a'];
        for(int i = 1,len;i <= m;++i){
            len = lsh[i],mp[i].clear();
            ll Ha = 0;
            for(int j = 1;j+len-1 <= n;++j){
                Ha = (H[j+len-2] - H[j]) ^ qz2[s[j]-'a'] ^ qz3[s[j+len-1]-'a'];
                mp[i][Ha] = 1;
            }
        }
        for(int i = 1,len,ls;i <= L;++i){
            len = t[i].length()-1,ls = get(len);
            ll Ha = 0;
            for(int j = 2;j < len;++j) Ha = Ha + qz1[t[i][j]-'a'];
            Ha = Ha ^ qz2[t[i][1]-'a'] ^ qz3[t[i][len]-'a'];
            if(mp[ls].count(Ha) == 0) continue;
            ++ans;
        }
        cout << "Case #" << iii << ": " << ans << '\n';
    }
    return 0;
}

:::: 可惜它 MLE 了，因为空间并不像时间一样是正常题目的十几倍。

那就换个思路，对有意义的长度，记录哪些哈希值代表了单词，然后遍历原串的时候查一下就行。

::::info[AC 代码]

#include <bits/stdc++.h>
using namespace std;
mt19937 gen(time(0)^78623473);
#define ll long long
#define modd 998244353
int T,L,n,A,B,C,D,x[1000005];
int ans,lsh[20005],m,qz1[26],qz2[26],qz3[26];
ll H[1000005];
unordered_map<ll,int>mp[450];
string t[20005];
char s[1000005];
void read(){
    cin >> L;
    for(int i = 1;i <= L;++i) cin >> t[i];
    for(int i = 1;i <= L;++i) t[i] = " " + t[i];
    cin >> s[1] >> s[2] >> n >> A >> B >> C >> D;
    const int mod = D;
    x[1] = s[1],x[2] = s[2],ans = 0;
    for(int i = 3;i <= n;++i) x[i] = ((ll)A * (ll)x[i-1] % mod + (ll)B * (ll)x[i-2] % mod + (ll)C) % mod;
    for(int i = 3;i <= n;++i) s[i] = (97 + x[i] % 26);
}
int get(const int X){
    int l = 1,r = m,mid;
    while(l < r){
        mid = ((l+r)>>1);
        if(X == lsh[mid]) return mid;
        else if(X > lsh[mid]) l = mid+1;
        else r = mid-1;
    }
    return l;//impossible
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> T;
    for(int iii = 1;iii <= T;++iii){
        read();
        for(int i = 0;i <= 25;++i) qz1[i] = gen() % modd,qz2[i] = gen() % modd,qz3[i] = gen() % modd;
        for(int i = 1;i <= L;++i) lsh[i] = (int)t[i].length()-1;
        sort(lsh+1,lsh+L+1),m = unique(lsh+1,lsh+L+1) - lsh - 1;
        for(int i = 1;i <= n;++i) H[i] = H[i-1] + qz1[s[i]-'a'];
        for(int i = 1;i <= m;++i) mp[i].clear();
        for(int i = 1,len,ls;i <= L;++i){
            len = t[i].length()-1,ls = get(len);
            ll Ha = 0;
            for(int j = 2;j < len;++j) Ha = Ha + qz1[t[i][j]-'a'];
            Ha = Ha ^ qz2[t[i][1]-'a'] ^ qz3[t[i][len]-'a'];
            mp[ls][Ha] += 1;
        }
        for(int i = 1,len;i <= m;++i){
            len = lsh[i];
            ll Ha = 0;
            for(int j = 1;j+len-1 <= n;++j){
                Ha = (H[j+len-2] - H[j]) ^ qz2[s[j]-'a'] ^ qz3[s[j+len-1]-'a'];
                if(mp[i].count(Ha) == 0) continue;
                if(mp[i][Ha] == 0) continue;
                ans += mp[i][Ha],mp[i][Ha] = 0;
            }
        }
        cout << "Case #" << iii << ": " << ans << '\n';
    }
    return 0;
}

::::