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

· · 题解

被自己学校OJ的毒瘤测评姬卡到自闭

Hash+栈+优化暴力

其实思路也很简单，就是把单词存进一个结构体，记录其哈希值和长度，然后就可以开始匹配了

但是，理论复杂度很高，为O(n*length)虽然实际体验效果不错

所以，为了卡过自家学校的OJ，加了一点小优化

额外维护一个数组num[i],记录以单词结尾字符的ascll码值为i的单词编号

这样的话，每次遍历的时候的元素个数，就会大大小于单词总个数，会比朴素算法快很多，虽然最坏复杂度还是O(n*length)

不过还是祝愿我早日肝出AC自动机（我太菜了）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#pragma GCC optimize(3)
#pragma G++ optimize(3)
using namespace std;
const int base=131;
char a[1000010],b[1000010];
typedef unsigned long long ull;
char ans[1000010];
int lena,lenb,cnt;
ull ba[1000010];
ull h[1000010];
struct cc{
    int len;
    ull has;
}w[100010];
int g[300][1000],tot[300];
int main()
{
    int n;
    scanf("%s",a+1);
    lena=strlen(a+1);
    scanf("%d",&n);
    for(register int i=1;i<=n;++i)
    {
        scanf("%s",b+1);
        w[i].len=strlen(b+1);
        ba[0]=1;
        for(register int j=1;j<=w[i].len;++j)
            w[i].has=w[i].has*base+b[j];//求每个单词的哈希值
        ++tot[b[w[i].len]];
        g[b[w[i].len]][tot[b[w[i].len]]]=i;//统计单词
    }
    for(register int i=1;i<=100000;++i)
        ba[i]=ba[i-1]*base;
    for(register int i=1;i<=lena;++i)
    {
        ++cnt;
        ans[cnt]=a[i];
        h[cnt]=h[cnt-1]*base+a[i];
        int q=tot[a[i]];
        for(register int j=1;j<=q;++j)//优化暴力
        {
            if(cnt-w[g[a[i]][j]].len>=0&&w[g[a[i]][j]].has==h[cnt]-h[cnt-w[g[a[i]][j]].len]*ba[w[g[a[i]][j]].len])
                cnt-=w[g[a[i]][j]].len;
        }
    }    
    for(register int i=1;i<=cnt;++i)
    putchar(ans[i]);
    putchar("\n");
    return 0;
}