【HDU 5716】带可选字符的多字符串匹配

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5716
神犇题解:http://www.cnblogs.com/clrs97/p/5985648.html

解题报告

这货$KMP$是不可做的,于是考虑用$bitset$来优化暴力
定义$v[i][j]$为文本串第$i$位是否能匹配模式串第$j$位
定义$f[i][j]$为第$i$种字符能否匹配模式串第$j$位
那么$v[i][j] = v[i – 1][j – 1] \ and \ f[s[i]][j]$
然后数组第二维用$bitset$优化,时间复杂度:$O(\frac{nm}{64})$

Code

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

const int N = 2000009;
const int M = 600;
const int SGZ = 100;

char s[N], sgz[SGZ];
bitset<M> v, f[SGZ];

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

inline int id(char c) {
	if ('0' <= c && c <= '9') {
		return c - '0' + 1;
	} else if ('a' <= c && c <= 'z') {
		return c - 'a' + 11;
	} else if ('A' <= c && c <= 'Z'){
		return c - 'A' + 37;
	} else {
		return 0;
	}
}

int main() {
	while (gets(s + 1)) {
		int n = strlen(s + 1), m = read();
		v.reset();
		for (int i = 0; i < SGZ; i++) {
			f[i].reset();
		}
		for (int i = 1; i <= m; i++) {
			int SGZ = read();
			scanf("%s", sgz + 1);
			for (int j = 1; j <= SGZ; j++) {
				f[id(sgz[j])][i] = 1;
			}
		}
		bool CantMatch = 1;
		for (int i = 1; i <= n; i++) {
			v = (v << 1) & f[id(s[i])];
			v[1] = f[id(s[i])][1];
			if (v[m]) {
				printf("%d\n", i - m + 1);
				CantMatch = 0;
			}
		}
		if (CantMatch) {
			puts("NULL");
		}
		getchar();
	}
	return 0;
}

—————————— UPD 2017.7.3 ———————————
这题的简单拓展:http://www.lydsy.com/JudgeOnline/problem.php?id=4924

262 thoughts to “【HDU 5716】带可选字符的多字符串匹配”

  1. Wow that was odd. I just wrote an extremely long comment but after
    I clicked submit my comment didn’t appear.
    Grrrr… well I’m not writing all that over again. Anyhow, just wanted to say excellent blog!

  2. I was curious if you ever considered changing the
    structure of your website? Its very well written; I love what youve got to say.
    But maybe you could a little more in the way of content so people
    could connect with it better. Youve got an awful lot of text for only
    having one or two pictures. Maybe you could space it
    out better?

  3. Ahaa, its fastidious conversation on the topic of this paragraph at this place at
    this webpage, I have read all that, so now me also commenting here.

  4. Have you ever considered about adding a little bit more than just your articles?
    I mean, what you say is valuable and everything.
    However imagine if you added some great photos or video clips to give your posts more,
    “pop”! Your content is excellent but with images and video clips, this website could
    certainly be one of the most beneficial in its field. Wonderful blog!

  5. Hello there, I do think your web site may be having web browser compatibility
    issues. Whenever I take a look at your site in Safari, it
    looks fine but when opening in IE, it’s got some overlapping issues.
    I just wanted to provide you with a quick heads up!

    Besides that, excellent blog!

  6. Hmm is anyone else experiencing problems with the pictures on this blog loading?
    I’m trying to figure out if its a problem on my end or if it’s the
    blog. Any feed-back would be greatly appreciated.

  7. Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point.
    You clearly know what youre talking about, why throw away your
    intelligence on just posting videos to your weblog when you
    could be giving us something informative to read?

  8. Hey I know this is off topic but I was wondering if you knew of any widgets
    I could add to my blog that automatically tweet my newest twitter updates.
    I’ve been looking for a plug-in like this for quite some time and was
    hoping maybe you would have some experience with something like this.
    Please let me know if you run into anything.
    I truly enjoy reading your blog and I look forward to your new updates.

  9. I do not even know how I stopped up right here, but I thought this post
    was good. I don’t realize who you are however certainly you
    are going to a well-known blogger if you happen to are not already.
    Cheers!

  10. Your style is really unique compared to other people I have read stuff
    from. Thank you for posting when you have the
    opportunity, Guess I’ll just book mark this web site.

  11. I think what you posted made a bunch of sense.
    But, what about this? suppose you added a little content? I ain’t
    suggesting your information isn’t solid, however what if you
    added a post title that makes people want more? I mean 【HDU 5716】带可选字符的多字符串匹配 – Qizy's
    Database is kinda boring. You might look at Yahoo’s home page and note how they write news
    headlines to grab people to click. You might add a related video or a pic or two to get people excited about what you’ve written. Just
    my opinion, it would bring your blog a little bit more interesting.

  12. Its like you read my thoughts! You appear to
    understand a lot approximately this, such as you wrote the e-book in it or something.
    I believe that you simply could do with some % to drive the
    message home a bit, however other than that, that is magnificent blog.
    A great read. I will certainly be back.

  13. Greetings I am so grateful I found your website, I really found you by error, while I
    was researching on Google for something else, Anyhow I am here now
    and would just like to say kudos for a remarkable post and
    a all round thrilling blog (I also love the theme/design), I don’t have time
    to go through it all at the minute but I have saved it and also
    added your RSS feeds, so when I have time I will
    be back to read much more, Please do keep up the excellent b.
    plenty of fish natalielise

  14. Hey there, I think your blog might be having browser compatibility issues.
    When I look at your blog site in Opera, it looks fine but when opening in Internet Explorer, it has some overlapping.
    I just wanted to give you a quick heads up! Other then that, very good blog!

  15. Greetings I am so delighted I found your web site, I
    really found you by error, while I was researching on Aol for something else,
    Anyways I am here now and would just like to say thanks a lot for a fantastic post and a all round interesting blog (I also love the theme/design), I don’t have
    time to go through it all at the moment but I have
    saved it and also included your RSS feeds, so when I have time I will be back to
    read more, Please do keep up the fantastic work.

  16. This is the right website for anybody who really wants to find out about this topic.
    You understand a whole lot its almost hard to argue with you
    (not that I really would want to…HaHa). You certainly put a brand new spin on a subject that has been discussed
    for a long time. Wonderful stuff, just excellent!

  17. Hi! I’m at work surfing around your blog from my new iphone 3gs!
    Just wanted to say I love reading your blog and look
    forward to all your posts! Keep up the superb work!

  18. Please let me know if you’re looking for a author for your weblog.
    You have some really good posts and I think 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.
    Many thanks!

  19. We absolutely love your blog and find many of your post’s to
    be exactly I’m looking for. Does one offer guest writers to write content in your case?
    I wouldn’t mind writing a post or elaborating on most of the subjects you write
    in relation to here. Again, awesome weblog! plenty of fish natalielise

  20. Heya i’m for the first time here. I came across this board
    and I find It really useful & it helped me out much.
    I hope to give something back and aid others like you helped me.

  21. Thanks for your personal marvelous posting! I quite enjoyed reading
    it, you are a great author.I will make sure to bookmark your blog and may come back down the road.

    I want to encourage you continue your great work, have a nice morning!

  22. I do consider all of the ideas you have offered for your
    post. They’re very convincing and can certainly work.
    Still, the posts are very quick for starters.
    Could you please extend them a bit from subsequent time? Thanks for
    the post.

  23. Hey! I know this is kinda off topic but I’d figured I’d ask.
    Would you be interested in exchanging links or maybe guest
    authoring a blog post or vice-versa? My website goes over a lot of
    the same topics as yours and I believe we could greatly benefit from
    each other. If you might be interested feel free to send me an email.

    I look forward to hearing from you! Terrific blog by the way!

  24. What’s up i am kavin, its my first time to commenting
    anywhere, when i read this piece of writing i thought i could also create comment due to this sensible paragraph.

  25. Hey There. I found your blog using msn. This is an extremely well written article.
    I’ll be sure to bookmark it and come back to read more of your useful information. Thanks for the
    post. I’ll definitely return.

  26. Hey just wanted to give you a quick heads up.
    The words in your content seem to be running off the screen in Internet
    explorer. I’m not sure if this is a formatting issue or something to do with web browser compatibility but I thought
    I’d post to let you know. The style and design look great though!
    Hope you get the problem solved soon. Thanks

  27. I was extremely pleased to find this page. I wanted to thank you for
    your time due to this fantastic read!! I definitely appreciated every little bit of it
    and i also have you book-marked to look at new things
    on your site.

  28. I’m truly enjoying the design and layout of your blog.
    It’s a very easy on the eyes which makes it much more enjoyable
    for me to come here and visit more often.
    Did you hire out a developer to create your theme?
    Exceptional work!

  29. I just couldn’t go away your site prior to suggesting that I actually loved the usual information a person supply toyour guests? Is going to be back often to investigatecross-check new posts

  30. I and also my friends ended up going through the good tips on your web site and so immediately developed a terrible feeling I had not thanked the web site owner for those techniques. Most of the women happened to be for that reason very interested to see them and have in actuality been loving those things. Appreciate your truly being well kind and also for pick out such essential topics most people are really desperate to learn about. My very own sincere apologies for not expressing gratitude to you earlier.

  31. Hey there, I think your site might be having browser compatibility issues.

    When I look at your blog in Chrome, it looks fine but when opening in Internet Explorer, it
    has some overlapping. I just wanted to give you a quick heads up!

    Other then that, fantastic blog!

  32. I loved as much as you will receive carried out right here.
    The sketch is tasteful, your authored material stylish.

    nonetheless, you command get got an shakiness over
    that you wish be delivering the following. unwell unquestionably come more formerly again as exactly the same
    nearly very often inside case you shield this increase.

  33. Having read this I thought it was very informative.
    I appreciate you spending some time and effort to put this content together.
    I once again find myself spending a significant amount
    of time both reading and posting comments. But so what, it was
    still worth it!

  34. I’ll immediately take hold of your rss feed as I can not find your e-mail subscription link or e-newsletter service.
    Do you’ve any? Please permit me recognize in order that I may just
    subscribe. Thanks.

  35. We stumbled over here from a different website and thought
    I should check things out. I like what I see so i am just following you.
    Look forward to going over your web page for a second time.

发表评论

电子邮件地址不会被公开。 必填项已用*标注