SCU 4438 Censor(Hash)题解

时间:2022-02-01 20:48:41

题意:找出字符串p中的w串删除,反复操作,直到找不到w,输出这个串

思路:哈希处理前缀和,如果值相同就删掉。

代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<vector>
using namespace std;
typedef unsigned long long ull;
const int maxn = 5e6 + ;
const ull seed = ;
ull bin[maxn], Hash[maxn];
char p[maxn], w[maxn], ans[maxn];
void init(){
bin[] = ;
for(int i = ; i < maxn; i++)
bin[i] = bin[i - ] * seed;
}
int main(){
init();
while(~scanf("%s%s", w + , p + )){
int lenw = strlen(w + ), len = strlen(p + );
ull aim = ;
if(lenw > len){
printf("%s\n", p + );
}
else{
int point = ;
for(int i = ; i <= lenw; i++)
aim = aim * seed + w[i] - 'a';
Hash[] = ;
for(int i = ; i <= lenw - ; i++){
Hash[point] = Hash[point - ] * seed + p[i] - 'a';
ans[point++] = p[i];
}
for(int i = lenw; i <= len; i++){
Hash[point] = Hash[point - ] * seed + p[i] - 'a';
ans[point] = p[i];
if(point >= lenw && Hash[point] - Hash[point - lenw] * bin[lenw] == aim){
point -= lenw;
}
point++;
}
for(int i = ; i < point; i++){
printf("%c", ans[i]);
}
printf("\n");
}
}
return ;
}