[笔记] P4824 [USACO15FEB] Censoring S

P4824 [USACO15FEB] Censoring S

事实上，此题和括号匹配非常像，都是“反复找到某东西并将其删除，直到删干净”。类似的题目还有abc454_d (xx) 。

而对于这种问题，最简单的方法就是用栈维护。

本题同理，开一个栈，把 \(S\) 中的字符挨个入栈，入栈后用字符串哈希，判断一下栈中最顶上的 \(|T|\) 个字符和 \(T\) 是否匹配即可。

p4824

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define ull unsigned long long
using namespace std;const int N=1e6+10;
string s,t;
char st[N];
ull p[N], h[N],ht;
int n,m,ans,tot;ull Hash(int l, int r){return h[r]-h[l-1]*p[r-l+1];
}signed main(){cin.tie(0)->sync_with_stdio(0);cin>>s; s=" "+s; cin>>t; t=" "+t;n=(int)s.size()-1; m=(int)t.size()-1;p[0]=1;for(int i=1; i<=n; i++) p[i]=p[i-1]*131;for(int i=1; i<=m; i++) ht=ht*131+t[i];for(int i=1; i<=n; i++){st[++tot]=s[i];h[tot]=h[tot-1]*131+s[i];while(1){if(tot<m) break;if(Hash(tot-m+1, tot)==ht) tot-=m;else break;}}for(int i=1; i<=tot; i++) cout<<st[i];return 0;
}