【BZOJ 3940】[Usaco2015 Feb] Censoring

Qizy AC Automaton, 字符串, 解题报告

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3940

解题报告

用栈和AC自动机来模拟即可

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int SGZ = 26;

char ctn[N], wrd[N]; 

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

class AC_Automaton{
int Root, cnt, ch[N][SGZ], apt[N], dep[N], fail[N];
queue<int> que;
public:
	inline void insert(char *s, int len) {
		int w = Root;
		for (int i = 1; i <= len; i++) {
			int  cc = s[i] - 'a';
			if (!ch[w][cc]) {
				ch[w][cc] = ++cnt;
				dep[cnt] = dep[w] + 1;
			}
			w = ch[w][cc];
		}
		apt[w] = len;
	}
	inline void build() {
		for (int i = 0; i < SGZ; i++) {
			if (ch[Root][i]) {
				que.push(ch[Root][i]);
			}
		}
		for (; !que.empty(); que.pop()) {
			int w = que.front();
			for (int i = 0; i < SGZ; i++) {
				if (ch[w][i]) {
					fail[ch[w][i]] = ch[fail[w]][i];
					apt[ch[w][i]] = max(apt[ch[w][i]], apt[fail[ch[w][i]]]);
					que.push(ch[w][i]);
				} else {
					ch[w][i] = ch[fail[w]][i];
				}
			}
		}
	}
	inline int root() {
		return Root;
	}
	inline int move(int &w, int cc) {
		w = ch[w][cc];
		return apt[w];
	}
}aca;

int main() {
	scanf("%s", ctn + 1);
	int n = read(), m = strlen(ctn + 1);
	for (int i = 1; i <= n; i++) {
		scanf("%s", wrd + 1);
		aca.insert(wrd, strlen(wrd + 1));
	}
	aca.build();
	vector<int> ans, pos;
	for (int i = 1; i <= m; i++) {
		int w = pos.empty()? aca.root(): *--pos.end();
		int len = aca.move(w, ctn[i] - 'a');
		ans.push_back(ctn[i]);
		pos.push_back(w);
		for (int j = 1; j <= len; j++) {
			ans.pop_back();
			pos.pop_back();
		}
	}
	for (int i = 0; i < (int)ans.size(); i++) {
		putchar(char(ans[i]));
	}
	return 0;
}

257 thoughts to “【BZOJ 3940】[Usaco2015 Feb] Censoring”

  37. Hello! I’ve been reading your website for a while now and finally got the bravery to go ahead and
    give you a shout out from Austin Tx! Just wanted to say keep up the excellent work!

    Reply

  68. What’s up everyone, it’s my first pay a quick visit at this website, and post is truly fruitful designed for me,
    keep up posting such articles or reviews.

    Reply

  78. Please let me know if you’re looking for a writer for your site.
    You have some really good articles and I feel I would be a good asset.

    If you ever want to take some of the load off, I’d absolutely love to write some articles for your
    blog in exchange for a link back to mine. Please shoot me an e-mail
    if interested. Cheers!

    Reply

  127. Pretty nice post. I simply stumbled upon your weblog and
    wished to mention that I’ve really loved browsing your blog posts.
    After all I will be subscribing for your feed and I am hoping you write again very soon!

    Reply

  143. I know this if off topic but I’m looking into starting my own blog and was curious what all is needed to get set up?

    I’m assuming having a blog like yours would cost a pretty penny?
    I’m not very web smart so I’m not 100% sure. Any tips or advice would be greatly
    appreciated. Kudos

    Reply

  144. Greetings I am so delighted I found your web site, I really found
    you by accident, while I was browsing on Digg for
    something else, Nonetheless I am here now and would just like to say
    kudos for a fantastic post and a all round exciting
    blog (I also love the theme/design), I don’t have
    time to read through it all at the minute but I have saved it and
    also included your RSS feeds, so when I have time I will be back to read a lot more, Please do keep up the great
    work.

    Reply

  186. great put up, very informative. I ponder why the opposite specialists of this sector don’t notice this. You must continue your writing. I am confident, you have a great readers’ base already!

    Reply

  188. Wow, incredible blog structure! How long haveyou been running a blog for? you make running a blog glance easy.The overall look of your web site is excellent, let alonethe content!

    Reply

  191. Hello! Quick question that’s entirely off topic. Do you know how to make your site mobile friendly? My website looks weird when browsing from my iphone 4. I’m trying to find a theme or plugin that might be able to correct this problem. If you have any suggestions, please share. Thanks!

    Reply

  194. Please leet me know if you’re looking for a article writer for yourweblog. Youu have some really good posts and I believe I wouldbe a good asset. If you ever want to take some of the load off, I’d really like to write skmearticles for your blog in exchange for a link back to mine.Please send me ann email if interested. Thanks!

    Reply

  204. cash advance payday loans online cash check short term loans [url=https://zxepersonalloansonlinesmall.com/]payday loans no credit check no employment verification[/url] ’

    Reply

  220. Thank you for the auspicious writeup. It if truth be told was a leisure account it. Glance advanced to far brought agreeable from you! However, how could we keep in touch?|

    Reply

  232. I was recommended this website by my cousin. I am not sure whether this post is written by him as no one else know such detailed about my trouble. You are wonderful! Thanks!

    Reply

  233. May I just say what a comfort to find somebody that actually understands what they are talking about over the internet. You certainly realize how to bring an issue to light and make it important. A lot more people really need to check this out and understand this side of the story. It’s surprising you are not more popular given that you definitely have the gift.|

    Reply

  234. Fascinating blog! Is your theme custom made or did you download it from somewhere? A design like yours with a few simple adjustements would really make my blog shine. Please let me know where you got your design. Thanks a lot|

    Reply

  238. Hey There. I found your blog using msn. That is an extremely neatly written article. I will be sure to bookmark it and come back to read extra of your useful info. Thank you for the post. I’ll definitely return.|

    Reply

  240. obviously like your web-site however you have to check the spelling on several of your posts. Many of them are rife with spelling problems and I to find it very troublesome to inform the truth nevertheless I will certainly come back again.

    Reply

  247. Heya i am for the first time here. I found this board and I find It really useful & it helped me out a lot. I hope to give something back and aid others like you aided me.|

    Reply

  252. I know this if off topic but I’m looking into starting my own weblog and was wondering what all is needed to get setup? I’m assuming having a blog like yours would cost a pretty penny? I’m not very internet savvy so I’m not 100 sure. Any recommendations or advice would be greatly appreciated. Many thanks|

    Reply

  255. It’s genuinely very complex in this busy life to listen news on TV, therefore I simply use web for that reason, and take the latest information.|

    Reply

  256. You have made some good points there. I checked on the net for more information about the issue and found most people will go along with your views on this website.|

    Reply

  257. When I originally commented I appear to have clicked the -Notify me when new comments are added- checkbox and now every time a comment is added I recieve 4 emails with the exact same comment. Is there a means you can remove me from that service? Thanks!|

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *