【Hash\KMP\线段树】文明的复兴

线段树】文明的复兴"/>

【Hash\KMP\线段树】文明的复兴

文明的复兴

(words.pas/in/out)

Problem

战神Prince&Gush回归了，但许多原先的上层精灵越来越不安分。他们无法忍受失去权力的空虚感，开始重新寻找新的途径获取权利。他们直率急躁的领导人King_Bette开始公开抨击权威，并散布谣言。 权利的统治需要统一，需要强硬，被逼无奈下正义的领袖开始收缴反动的资料，清除世界的毒瘤，借以踏上快速发展之路。

不良信息指的是一组单词，每个单词均为不良信息。不良信息文本是指包含一系列的单词，且其中包含有不良信息。发布信息者经常在单词中加些字母以外的字符以搅乱正义的视线，于是Prince想请你为他写一个能够将这些不良信息屏蔽掉的工具。但是为了尽量降低误删率,他提出了下面一个要求：你只需要将字母完全匹配的单词屏蔽掉即可。

例如:

sex为不良信息时,sex8,sex$,se#x均为不良信息sexx 则不属于不良信息.

Input

第一行为一个正数k <= 10000，表示有k个需要被屏蔽的词语，均为小写字母。

以下k行每行一个单词。

最后一行为输入需要处理的文本（文本长度<=100000）,单词与单词之间空格分开且所有字母为小写字母。

Output

输出一行和输入格式一致的文本，被屏蔽的单词的字母以*代替原字母。

Sample Input

1

sex

sex sex8 sex$ s&&ex sexx aaa bbb

Sample Output

*** ***8 ***$ *&&** sexx aaa bbb

这道题题目描述极为不清晰。如果按照我的理解，这就该是一道好题，但是按照出题者的意思，这只是一道水题。

出题者的意思是一个单词必须找到和它完全匹配的，才能够和谐掉。如这组数据：

2

sex fuck

sex&&fuck are both about sex

答案是sex&&fuck are both about ***

而题意不清晰，让很多人以为应该是：

***&&**** are both about ***。

因此按照出题者的意思。只需要hash映射就完了。

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <set>
using std::string;
using std::set;set<string> hash;
string source;
char src[100010];
char str[100010];int main()
{freopen("words.in","r",stdin);freopen("words.out","w",stdout);long k;scanf("%ld",&k);for (long i=1;i<k+1;i++){long len = 0;long i = 0;scanf("%s",src+1);while (src[++len])src[++i] = src[len];src[++i] = 0;source = string(src+1);hash.insert(source);}while (scanf("%s",src+1)!=EOF){long i = 0;long len = 0;while (src[++len])if (isalpha(src[len]))str[++i] = src[len];str[++i] = 0;source = string(str+1);if (hash.find(source)!=hash.end()){for (i=1;i<len;++i){if (isalpha(src[i]))printf("*");elseprintf("%c",src[i]);}}else{printf("%s",src+1);}printf(" ");}return 0;
}

而按照较为合理的解释来做的话。严重超时。但是它确实更合理。

考虑到可能出现这种情况：

2

sex exchange

sexchange

应该整个单词都会被和谐掉，所以设计出以下方法：

先把原串合为一个字符串，把Kmp稍作改造，如果遇到原串中出现了符号，且模式串还未匹配完毕，则只修改原串的指针。如果匹配成功一次的话，则用线段树标记一次，并将模式串指针归零。

#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>void next_init(char *words,long lenw,long *next)
{long k = 0;long j = 1;while (j < lenw+1){if (k==0 || words[j]==words[k]){j ++;k ++;next[j] = k;}else k = next[k];}
}char tree[4000010];void brush(long l,long r,long i,long ll,long rr)
{long mid = (l+r)>>1;if (ll<=l && rr>=r){tree[i] = 1;return;}if (rr < mid+1){brush(l,mid,i<<1,ll,rr);}if (ll > mid){brush(mid+1,r,(i<<1)+1,ll,rr);}if (ll<=mid && rr>mid){brush(l,mid,i<<1,ll,rr);brush(mid+1,r,(i<<1)+1,ll,rr);}if (tree[i<<1] == tree[(i<<1)+1])tree[i] = tree[i<<1];elsetree[i] = 2;
}void output(long l,long r,long i,char *a)
{if (l == r){if (isalpha(a[l]) && tree[i]==1)printf("*");elseprintf("%c",a[l]);return;}if (tree[i] < 2){for (long j=l;j<r+1;j++){if (isalpha(a[j]) && tree[i]==1)printf("*");elseprintf("%c",a[j]);}return;}long mid = (l+r)>>1;output(l,mid,i<<1,a);output(mid+1,r,(i<<1)+1,a);
}void kmp(char *a,long lena,char *b,long lenb,long *next)
{long i=1;long j=1;while (i<lena+1){if (j==0 || a[i]==b[j]){j ++;i ++;}else if (!isalpha(a[i]) && j<lenb+1){i ++;}else j = next[j];if (j == lenb+1){long q = i-1;for (long p=1;p<lenb+1;p++){while (!isalpha(a[q])) q--;q --;}q ++;if (!isalpha(a[q-1]) && !isalpha(a[i]))brush(1,lena,1,q,i-1);}}
}char source[10010][310];
long next[10010][310];
char words[1000010];
long lenth[1000010];int strcmpr(const void* a,const void* b)
{return strcmp((char*)a,(char*)b);
}long binary(long l,long r,char a)
{long rs = r+1;while (l <= r){long mid = (l+r)>>1;if (source[mid][1]>=a){if (rs > mid)rs = mid;r = mid-1;}elsel = mid+1;}return rs;
}int main()
{freopen("words.in","r",stdin);freopen("words.out","w",stdout);long k;scanf("%ld",&k);for (long i=1;i<k+1;i++){scanf("%s",source[i]+1);}qsort(source+1,k,sizeof(source[0])/sizeof(char),strcmpr);for (long i=1;i<k+1;i++){long j = 0;while (source[i][++j])if (isalpha(source[i][j]))source[i][++lenth[i]] = source[i][j];next_init(source[i],lenth[i],next[i]);}gets(words+1);gets(words+1);long lle = strlen(words+1);for (long i=binary(1,k,words[1]);source[i][1]==words[1] && i<k+1;i++)kmp(words,lle,source[i],lenth[i],next[i]);output(1,lle,1,words);return 0;
}