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

· · 题解

实测本题数据很水 自然溢出哈希可以过 又没看到有人发哈希的题解 所以来发一篇...（其实是因为本菜鸡调不出AC自动机）

首先扫描单词的时候把每个单词的Hash值预处理出来 然后跟它的长度一起存在结构体里，把结构体按照单词长度排序，然后在最后在栈里模拟的时候一个一个把原串中的字符推到栈里，只要大于最小的单词长度就可以开始哈希匹配，如果匹配成功就把这一段出栈。

总体的时间复杂度是O(n*串长) ，跑不满就是了......下面上代码。

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=100000+10;
const ll b=131;
ll Hash[maxn],Pow[maxn]={1};
char str[maxn],u[maxn],tmp[maxn];
struct Tmp
{
    int len;
    ll Hash;
}t[maxn];//结构体存单词
bool cmp(const Tmp & a,const Tmp & b)
{
    return a.len<b.len;
}
int ptr;
inline ll GetHash(int j,int i)
{
    return Hash[i]-Hash[j-1]*Pow[i-j+1];
}//计算子串哈希值
int main()
{
    scanf("%s",str+1);
    int n=strlen(str+1),m;
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%s",tmp+1);
        t[i].len=strlen(tmp+1);
        for(int j=1;j<=t[i].len;++j)
            t[i].Hash=t[i].Hash*b+tmp[j];
    }
    sort(t+1,t+1+m,cmp);
    for(int i=1;i<=n;++i)
        Pow[i]=(Pow[i-1]*b);
    for(int i=1;i<=n;++i)
    {
        u[++ptr]=str[i],Hash[ptr]=Hash[ptr-1]*b+u[ptr];
        while(ptr<t[1].len&&i<n)u[++ptr]=str[++i],Hash[ptr]=Hash[ptr-1]*b+u[ptr];
        //确保栈中字符数量大于最小的单词长度
        for(int j=1;j<=m&&ptr;++j)
            if(ptr-t[j].len+1>=1&&GetHash(ptr-t[j].len+1,ptr)==t[j].Hash){ptr-=t[j].len;}
            //匹配操作，若匹配则出栈
    }
    for(int i=1;i<=ptr;++i)
        putchar(u[i]);
    puts("");
    return 0;
}

第一次发题解求过...谢谢了