【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

423 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. 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.

  11. 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.

  12. 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

  13. 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!

  14. 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.

  15. 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!

  16. 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!

  17. 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!

  18. 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

  19. 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.

  20. 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!

  21. 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.

  22. 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!

  23. 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.

  24. 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.

  25. 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

  26. 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.

  27. 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!

  28. 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

  29. 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.

  30. 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!

  31. 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.

  32. 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!

  33. 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.

  34. 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.

  35. Howdy! I know this is kinda off topic but I was wondering if you knew where I could find a captcha plugin for my comment form? I’m using the same blog platform as yours and I’m having problems finding one? Thanks a lot!

  36. Hello there! I could have sworn I’ve been to this blog before but after browsing
    through some of the post I realized it’s new to me.

    Anyhow, I’m definitely delighted I found it and
    I’ll be bookmarking and checking back often!

  37. Hey There. I found your weblog using msn. This is a really neatly written article.
    I will make sure to bookmark it and return to read more of your helpful
    info. Thanks for the post. I’ll definitely return.

  38. My developer is trying to convince me to move to .net from PHP.
    I have always disliked the idea because of the costs.
    But he’s tryiong none the less. I’ve been using WordPress on a number of websites for about a
    year and am nervous about switching to another platform.
    I have heard excellent things about blogengine.net.
    Is there a way I can import all my wordpress content into it?
    Any kind of help would be greatly appreciated!

  39. I get pleasure from, result in I found exactly what I was taking a look for.

    You’ve ended my 4 day lengthy hunt! God Bless you man. Have a great day.
    Bye

  40. I know this if off topic but I’m looking into starting my own weblog and was wondering what all
    is required to get setup? I’m assuming having a blog like yours would cost a pretty penny?
    I’m not very web smart so I’m not 100% certain. Any suggestions or advice would
    be greatly appreciated. Thanks

  41. Wow, fantastic blog format! How long have you ever been blogging for?

    you make running a blog glance easy. The entire glance of your site is wonderful,
    as neatly as the content material!

  42. Thank you for the good writeup. It in truth used to be a leisure account it.
    Glance complex to more introduced agreeable from you! However, how can we keep up a correspondence?

  43. Do you have a spam issue on this blog; I also am a blogger, and
    I was wondering your situation; we have created some nice procedures
    and we are looking to exchange techniques with other folks, why not
    shoot me an email if interested.

  44. Every weekend i used to pay a quick visit this web page, because
    i wish for enjoyment, since this this web site conations actually fastidious funny data too.

  45. Just desire to say your article is as astounding. The clearness in your post is simply cool and
    i could assume you’re an expert on this subject.
    Well with your permission let me to grab your RSS feed to keep up to date with forthcoming post.
    Thanks a million and please carry on the gratifying work.

  46. Simply desire to say your article is as astounding.
    The clarity in your post is simply spectacular and i can assume you’re an expert on this subject.

    Fine with your permission let me to grab your feed to keep up to date with forthcoming post.
    Thanks a million and please keep up the rewarding work.

  47. Hi there! This is my first comment here so I just
    wanted to give a quick shout out and say I really enjoy reading through your
    posts. Can you recommend any other blogs/websites/forums that deal with
    the same topics? Thanks!

  48. I do agree with all the concepts you’ve offered for your post.
    They are very convincing and will certainly work.
    Nonetheless, the posts are too short for novices. Could you please
    lengthen them a bit from next time? Thank you for the post.

  49. I don’t know if it’s just me or if everybody else experiencing problems with your blog.

    It seems like some of the written text in your content are
    running off the screen. Can someone else please provide feedback and let
    me know if this is happening to them too? This may be a
    problem with my internet browser because I’ve had this happen before.

    Thank you

  50. We’re a bunch of volunteers and starting a new scheme in our community.

    Your site provided us with useful information to work on. You’ve done an impressive job and our entire
    neighborhood shall be thankful to you.

  51. you’re in point of fact a good webmaster. The website loading speed is amazing.
    It kind of feels that you are doing any distinctive trick. Also, The
    contents are masterwork. you’ve performed a excellent activity on this matter!

  52. Appreciating the hard work you put into your website and detailed information you offer.

    It’s great to come across a blog every once in a while that isn’t the same out of date rehashed material.
    Great read! I’ve saved your site and I’m including your RSS feeds to my Google account.

  53. Yesterday, while I was at work, my sister stole my iPad and tested to see if it can survive a twenty five foot drop,
    just so she can be a youtube sensation. My iPad is now broken and she has 83 views.
    I know this is totally off topic but I had to share it with someone!

  54. Excellent blog! Do you have any recommendations for aspiring writers?

    I’m hoping to start my own blog soon but I’m a little lost on everything.
    Would you recommend starting with a free platform like WordPress or go for a paid option? There are so many options out there that I’m totally overwhelmed ..
    Any recommendations? Many thanks!

  55. I think this is one of the such a lot important info for me.
    And i’m glad reading your article. However wanna commentary on some normal issues, The
    site style is ideal, the articles is in point of fact excellent : D.
    Good task, cheers

  56. You are my aspiration, I have few blogs and infrequently run out from post :). “No opera plot can be sensible, for people do not sing when they are feeling sensible.” by W. H. Auden.

Leave a Reply to sistem gereksinimleri Cancel reply

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