【Codeforces 100548G】The Problem to Slow Down You

题目传送门:http://codeforces.com/gym/100548 ps:是G题

首先,这个题目肯定可以用manacher配合SA/SAM来完成,然而SA/SAM的代码不好写QAQ
但是我们发现,需要的所有串都是回文串,所以可以建两个PAM,然后一起跑DFS
1A 撒花! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 200000+9;
const int SIGMA_SIZE = 26;

struct Palindromic_Tree{
	#define PAM Palindromic_Tree
	int ch[MAXN][SIGMA_SIZE],fail[MAXN];
	int cnt,last,n,sz[MAXN],len[MAXN];
	char *pat; LL ret;
	
	inline int newnode(){
		cnt += 1;
		memset(ch[cnt],0,sizeof(ch[cnt]));
		fail[cnt] = sz[cnt] = len[cnt] = 0;
		return cnt;
	}
	
	inline void init(){
		cnt = last = 1; 
		fail[0] = fail[1] = 1;
		sz[0] = sz[1] = len[0] = 0; len[1] = -1;
		memset(ch[0],0,sizeof(ch[0]));
		memset(ch[1],0,sizeof(ch[1]));
	}
	
	inline void extend(int p, int c){
		int w = last;
		while (pat[p-len[w]-1] != pat[p]) w = fail[w];
		if (!ch[w]){
			int nw = newnode(),k=fail[w]; len[nw] = len[w]+2;
			while (pat[p-len[k]-1] != pat[p]) k = fail[k];
			fail[nw] = ch[k]; ch[w] = nw;
		}
		last = ch[w];
		sz[last]++;
	}
	
	inline void build(char *s){
		init(); pat = s;
		n = strlen(s+1);
		for (int i=1;i<=n;i++)
			extend(i,s[i]-'a');
		for (int i=cnt;i;i--)
			sz[fail[i]] += sz[i];
	}
	
	void DFS(int pa, int pb, PAM *s){
		if (pa > 1 && pb > 1) ret += (LL)sz[pa]*(LL)s->sz[pb];
		for (int i=0;i<SIGMA_SIZE;i++)
			if (ch[pa][i] && s->ch[pb][i])
				DFS(ch[pa][i],s->ch[pb][i],s);
	}
	
	inline LL solve(PAM *a){
		ret = 0LL;
		DFS(0,0,a);
		DFS(1,1,a);
		return ret;
	}
}A,B;

char sa[MAXN],sb[MAXN];

int main(){
	int T,TT=0; cin>>T;
	while (T--){
		scanf("%s%s",sa+1,sb+1);
		A.build(sa); B.build(sb);	
		printf("Case #%d: %I64d\n",++TT,A.solve(&B));
	}
	return 0;
} 

276 thoughts to “【Codeforces 100548G】The Problem to Slow Down You”

  1. My brother recommended I might like this blog.

    He was entirely right. This post actually made my day.
    You can not imagine simply how much time I had spent for this
    info! Thanks!

  2. This is very interesting, You are a very skilled blogger.
    I’ve joined your rss feed and look forward
    to seeking more of your excellent post. Also, I’ve shared your site in my social networks!

  3. Usually I don’t read post on blogs, however I wish to say that this write-up very forced me to take a look at and
    do so! Your writing taste has been amazed me.
    Thank you, quite nice post.

  4. I really like your blog.. very nice colors & theme.
    Did you make this website yourself or did
    you hire someone to do it for you? Plz respond as I’m looking to
    design my own blog and would like to know where u got this from.
    cheers

  5. I’m really impressed with your writing skills as well
    as with the layout on your weblog. Is this a paid theme or did you modify it yourself?

    Anyway keep up the excellent quality writing, it’s rare to see a great blog like this one nowadays.

  6. hello!,I like your writing very a lot! proportion we be in contact extra approximately your article on AOL?
    I require an expert in this area to unravel my problem. May be that is you!
    Looking ahead to peer you.

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

  8. What’s Taking place i’m new to this, I stumbled upon this I have discovered It positively helpful and it has helped me
    out loads. I hope to give a contribution & help other customers like its helped me.
    Great job.

  9. I’ve been exploring for a little for any high-quality articles or blog posts in this sort of house .
    Exploring in Yahoo I eventually stumbled upon this website.
    Reading this info So i am glad to show that I have a very just right uncanny feeling I came upon just
    what I needed. I so much certainly will make sure to do not forget this site and give
    it a look regularly.

  10. Hello there! I could have sworn I’ve been to this website
    before but after browsing through some of the post I realized it’s new to
    me. Anyhow, I’m definitely glad I found it and I’ll be bookmarking
    and checking back frequently!

  11. you’re really a excellent webmaster. The site loading speed is amazing.

    It seems that you are doing any distinctive trick.
    Furthermore, The contents are masterwork. you have done a wonderful job on this matter!

  12. Appreciating the persistence you put into your blog
    and detailed information you provide. It’s nice to
    come across a blog every once in a while that isn’t the same old rehashed information. Wonderful read!
    I’ve bookmarked your site and I’m adding your RSS feeds to my
    Google account.

  13. Do you have a spam problem on this website; I
    also am a blogger, and I was wondering your situation; we have developed some
    nice practices and we are looking to swap strategies with
    other folks, why not shoot me an email if interested.
    natalielise pof

  14. Hello! I just wanted to ask if you ever have any trouble
    with hackers? My last blog (wordpress) was hacked and I ended up losing months of hard work due to
    no data backup. Do you have any solutions to prevent hackers?

  15. wonderful post, very informative. I ponder why the
    other specialists of this sector don’t realize this.
    You should continue your writing. I’m confident, you have a huge readers’ base already!

  16. Aw, this was a very good post. Finding the time and actual effort to
    produce a really good article… but what can I say… I hesitate a lot and don’t manage to get nearly anything done.

  17. Hello There. I found your blog using msn. This is an extremely well written article.

    I will make sure to bookmark it and come back to read more
    of your useful information. Thanks for the post. I’ll certainly
    comeback.

  18. hey there and thank you for your info – I’ve certainly picked up something new from right here.
    I did however expertise a few technical points
    using this site, since I experienced to reload the website a lot of times
    previous to I could get it to load correctly. I had been wondering if
    your web hosting is OK? Not that I am complaining, but slow loading instances times will
    very frequently affect your placement in google and
    can damage your quality score if advertising and marketing with
    Adwords. Anyway I’m adding this RSS to my e-mail and
    can look out for much more of your respective intriguing content.

    Make sure you update this again soon.

  19. Wonderful blog! I found it while surfing around on Yahoo News.
    Do you have any suggestions on how to get listed
    in Yahoo News? I’ve been trying for a while but I never seem to get there!
    Thanks

  20. Does your website have a contact page? I’m having problems locating it but, I’d like
    to send you an email. I’ve got some creative
    ideas for your blog you might be interested in hearing. Either way, great website
    and I look forward to seeing it grow over time.

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

  22. Nice post. I learn something totally new and challenging on blogs I stumbleupon everyday.
    It will always be useful to read through articles from other authors and use a little something from other web
    sites.

  23. certainly like your web site however you need to test
    the spelling on quite a few of your posts. Several of them are
    rife with spelling issues and I to find it very bothersome to tell the reality however I’ll certainly come
    again again.

  24. I have been exploring for a little bit for any high quality articles or weblog posts in this sort of area .
    Exploring in Yahoo I eventually stumbled upon this site. Reading this information So i am happy to show that I’ve an incredibly good uncanny feeling I
    found out just what I needed. I so much without a
    doubt will make sure to don?t put out of your mind this site and provides it a look regularly.

  25. Greetings! I know this is somewhat off topic but I was wondering which blog platform are
    you using for this site? I’m getting tired of WordPress because
    I’ve had problems with hackers and I’m looking at alternatives for another platform.
    I would be fantastic if you could point me in the direction of a good platform.

  26. Hey there just wanted to give you a brief heads up
    and let you know a few of the images aren’t loading correctly.

    I’m not sure why but I think its a linking
    issue. I’ve tried it in two different web browsers and both show the same outcome.

  27. My partner and I stumbled over here by a different page and thought I should check things out.

    I like what I see so i am just following you. Look forward to finding out about your web page yet again.

  28. Woah! I’m really digging the template/theme of this website.

    It’s simple, yet effective. A lot of times it’s difficult to get that
    “perfect balance” between superb usability and appearance.
    I must say you have done a superb job with this.
    Additionally, the blog loads very fast for me on Safari.
    Exceptional Blog!

  29. My spouse and I stumbled over here by a different page and thought I
    might check things out. I like what I see so now i’m following you.

    Look forward to looking over your web page again.

  30. Great beat ! I would like to apprentice at the same time as
    you amend your site, how could i subscribe for
    a weblog site? The account helped me a appropriate deal.
    I were a little bit acquainted of this your broadcast provided brilliant clear concept

  31. Howdy I am so grateful I found your blog page, I really
    found you by accident, while I was searching on Aol
    for something else, Nonetheless I am here now and would just like
    to say kudos for a marvelous post and a all round entertaining blog
    (I also love the theme/design), I don’t have time
    to look over it all at the moment but I have bookmarked it and also
    added in your RSS feeds, so when I have time I will be back to read much
    more, Please do keep up the awesome b.

  32. My partner and I stumbled over here different web page and
    thought I may as well check things out. I like what I
    see so now i’m following you. Look forward to going over your web page repeatedly.

  33. Hey! Quick question that’s completely off topic. Do you know how to make your site mobile friendly?
    My website looks weird when browsing from my iphone4.
    I’m trying to find a template or plugin that might be
    able to resolve this issue. If you have any recommendations, please share.
    Thanks!

  34. Hey there just wanted to give you a quick heads up.
    The text in your article seem to be running off the screen in Chrome.
    I’m not sure if this is a formatting issue or something to do with browser compatibility but I figured
    I’d post to let you know. The layout look great though!

    Hope you get the issue solved soon. Cheers

  35. What i do not realize is actually how you are no longer
    really a lot more smartly-favored than you may be now. You are so intelligent.
    You already know therefore significantly in terms of this topic, made me individually imagine it from a lot
    of various angles. Its like men and women don’t seem to be fascinated
    unless it’s one thing to do with Girl gaga!
    Your personal stuffs nice. Always maintain it up!

  36. certainly like your web-site however you have to test the spelling
    on quite a few of your posts. A number of them are rife with spelling problems and I to find it very bothersome
    to tell the reality then again I’ll certainly come again again.

  37. Please let me know if you’re looking for a article writer for your weblog.
    You have some really great articles and I think I would be a
    good asset. If you ever want to take some of the load off, I’d love to
    write some content for your blog in exchange for a link
    back to mine. Please shoot me an e-mail if interested. Regards!

  38. Excellent web site you have got here.. It’s difficult to find high-quality writing like yours these days.
    I seriously appreciate people like you! Take care!!

  39. Thank you for the auspicious writeup. It actually was once
    a enjoyment account it. Look advanced to more brought agreeable from you!
    By the way, how could we be in contact?

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

  41. When someone writes an post he/she maintains the plan of a user in his/her mind that how a user can be aware of it.

    Therefore that’s why this post is perfect. Thanks!

  42. An impressive share, I simply given it into a colleague who wadd doing a bit of analysis in it. And he the truth is purchadded me breakfaddt add a result of I found it for him.. smile. So let me reword that: Thnx for the treat?! But yeah Thnkx for spending the time to discuss it, I feel stringly about it and love reading extra in it topic. If possible, add you change into experience, would you mind updating Vegus weblog with more details? It is extremely useful for me. Large thumb up for it blog post?!

  43. Hi, i believe that i saw you visited my website thus i got here to return the want?.I’m trying to find
    issues to improve my site!I guess its ok to make use of some of your ideas!!

  44. The world is like a hillside. As long as you are not standing at the apex, someone will always be taller than you. When you look up for a long time, you must look down at the right time. We are all ordinary people.

  45. I’ve been surfing online more than three hours today, yet I never found any interesting article like yours.
    It is pretty worth enough for me. In my view, if all site owners and bloggers made good content as you did, the web will be much more
    useful than ever before.

  46. Hello my friend! I want to say that this article is amazing, nice written and include approximately all important infos. I would like to see more posts like this.

发表评论

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