题解 P3121 【[USACO15FEB]审查（黄金）Censoring (Gold)】

· · 题解

用哈希做的，自认为码量较小：

#include<bits/stdc++.h>
using namespace std;
char s[10000001],t[10000001],u[10000001];
unsigned long long ha[10000001],hash[100000001],powe[10000001];
int n,t_len[100000001];
int base=2333333;
int main(){
    powe[0]=1;
    hash[0]=0;
    scanf("%s%d",s+1,&n);
    int cnt=0,s_len=strlen(s+1);
    for(int i=1;i<=n;i++){
        scanf("%s",t+1);
        t_len[i]=strlen(t+1);
    for(int j=1;j<=t_len[i];j++){
        if(!powe[j])
            powe[j]=powe[j-1]*base;
        ha[i]*=base;//求各个单词的哈希值
        ha[i]+=(unsigned long long)t[j];
    }
    }
    for(int i=1;i<=s_len;i++){
        u[++cnt]=s[i];
        hash[cnt]=hash[cnt-1]*base+(unsigned long long)s[i];
        for(int j=1;j<=n;j++){
        if(ha[j]==hash[cnt]-hash[cnt-t_len[j]]*powe[t_len[j]])//比较
                                                        //哈希值是否相等
            cnt-=t_len[j];//栈顶指针下压，弹出此单词
        }

    }
    for(int i=1;i<=cnt;i++)
        printf("%c",u[i]);
    printf("\n");//一定要换行！！！
    return 0;
}