洛谷 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;

}

巴特西

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

最新文章

热门文章