复杂度正确的hash做法 题解 P3121 【[USACO15FEB]审查（黄金）Censoring (Gold)】

· · 题解

已知的 hash 题解的复杂度都是假的,蒟蒻来一篇复杂度正确的 hash 做法，复杂度 O(|s|\sqrt n)。

将列表中的单词 t_i 按照长度从大到小排序（长度长的起点更靠前），然后 仿照弱化版 P4824 的做法，每次加入一个 s 中的字符用 hash 依次判断列表中的单词是否出现过。这样的时间复杂度是 O(|s|n)。

考虑优化上述做法，根据经典结论，记 t_i 的长度为 cnt_i。 则 cnt_i 的种类数不超过 \sqrt{ \sum |t_i|} 。我们开一个数组存下那些长度出现过，然后依次判断对应长度的 t_i 是否出现过即可。细节在代码注释里。

#include<bits/stdc++.h>
#define ull unsigned long long 
using namespace std;
const ull B=131;
unordered_map<ull,bool> mp;//判断对应hash值是否出现 
const int N=100005;
int n,m,len,tot,top,numlen[N];
//numlen记录出现过的长度，top是关于其的指针
//len是关于hs的指针
//tot是关于ans的指针 
string tmp,s;char ans[N];ull hs[N],pw[N];
void make_hash(string &s){
    int n=s.length();
    ull res=0;
    numlen[++top]=n;
    for(int i=0;i<n;++i)
        res=res*B+s[i]-'a'+1; 
    mp[res]=1;//记录此hash值出现过 
}
void check(int k){
    if(k>len)return;//如果长度不够直接返回 
    ull hash=hs[len]-hs[len-k]*pw[k];//这一段的hash值 
    if(!mp.count(hash))return;//判断是否出现 
    tot-=k,len-=k;//出现过则删除这段 
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>tmp>>n;while(n--){cin>>s;make_hash(s);}
    m=tmp.length();tmp=" "+tmp;pw[0]=1;
    for(int i=1;i<=m;++i)pw[i]=pw[i-1]*B;
    sort(numlen+1,numlen+1+top); 
    top=unique(numlen+1,numlen+1+top)-numlen-1;//去重 
    for(int i=1;i<=m;++i){
        ans[++tot]=tmp[i];++len;
        hs[len]=hs[len-1]*B+tmp[i]-'a'+1;
        for(int j=top;j>=1;--j)
            check(numlen[j]);//从长到短依次check 
    }
    for(int i=1;i<=tot;++i)putchar(ans[i]);
    return 0;
}