相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4212
神犇题解：http://www.cnblogs.com/yousiki/p/6550484.html
解题报告
这题如果没有强制在线，那么我们可以用$Trie + bitset$在$O(\frac{2000000n}{64})$的时间复杂度过
如果强制在线并且$s1,s2$等长，那么我们可以在$O(2000000 \log 2000000)$的时间复杂度过
现在解决原问题，先考虑一个暴力：
先把前缀能匹配上的串找出来，然后我们在其中找出后缀能匹配的串
考虑一下后缀数组：按字典序排序后，前缀能匹配上的一定是一个区间
于是我们可以先建一个正串的$Trie$，用来找出前缀合法的字符串区间
然后我们将反串建成一个持久化$Trie$，每一次用前缀合法的区间再去查后缀即可
另外还有一点$Trick$就是字符串排序：我们可以先将正串建成$Trie$，然后贪心$DFS$
这样排序的复杂度就可以是线性的，总的时间复杂度也就是线性的了
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2000009;
const int M = 2009;
const int SGZ = 26;
int n,m,tot,beg[M],sz[M],ord[M];
char s1[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
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 Trie{
int cnt,ch[N][26],mn[N],mx[N];
vector<int> id[N];
public:
inline void insert(char *s, int len, int ID) {
int w = 0;
for (int i=0;i<len;i++) {
int c = s[i] - 'a';
if (!ch[w]) ch[w] = ++cnt;
w = ch[w];
}
id[w].push_back(ID);
}
inline void sort(int w, int *arr, int &cur) {
for (int i=0;i<id[w].size();i++) {
arr[++cur] = id[w][i];
}
for (int i=0;i<SGZ;i++) {
if (ch[w][i]) {
sort(ch[w][i], arr, cur);
}
}
}
inline void mark(int val, char *s, int len) {
int w = 0;
for (int i=0;i<len;i++) {
int c = s[i] - 'a';
w = ch[w];
if (!mn[w] || mn[w] > val) mn[w] = val;
if (!mx[w] || mx[w] < val) mx[w] = val;
}
}
inline void query(char *s, int len, int &l, int &r) {
int w = 0;
for (int i=0;i<len;i++) {
int c = s[i] - 'a';
if (!ch[w]) {
l = 1; r = 0;
return;
} else {
w = ch[w];
}
}
l = mn[w];
r = mx[w];
}
private:
}trie;
class Persistent_Trie{
int cnt,root[M],sum[N],ch[N][26];
public:
inline void insert(int p, int w, char *s, int len) {
Insert(root[p], root[w], s, len);
}
inline int query(int l, int r, char *s, int len) {
if (l > r) return 0;
int ret = 0, w = root[r];
for (int i=0;i<len;i++) {
w = ch[w][s[i]-'a'];
}
ret += sum[w];
w = root[l-1];
for (int i=0;i<len;i++) {
w = ch[w][s[i]-'a'];
}
ret -= sum[w];
return ret;
}
private:
void Insert(int p, int &w, char *s, int len) {
w = ++cnt;
sum[w] = sum[p] + 1;
memcpy(ch[w], ch[p], sizeof(ch[w]));
if (len <= 0) return;
int c = s[len-1] - 'a';
Insert(ch[p], ch[w], s, len - 1);
}
}PTE;
int main() {
n = read();
for (int i=1,last=0;i<=n;i++) {
beg[i] = last;
scanf("%s", s1+last);
sz[i] = strlen(s1+last);
trie.insert(s1+last, sz[i], i);
last += sz[i];
}
tot = 0;
trie.sort(0, ord, tot);
for (int i=1;i<=n;i++) {
trie.mark(i, s1+beg[ord[i]], sz[ord[i]]);
PTE.insert(i-1, i, s1+beg[ord[i]], sz[ord[i]]);
}
m = read();
for (int tt=1,last=0,l,r;tt<=m;tt++) {
scanf("%s",s1);
int len = strlen(s1);
for (int i=0;i<len;i++) {
s1[i] = (s1[i] - 'a' + last) % SGZ + 'a';
}
trie.query(s1, len, l, r);
scanf("%s",s1);
len = strlen(s1);
for (int i=0,j=len-1;i<j;i++,j--) {
swap(s1[i], s1[j]);
}
for (int i=0;i<len;i++) {
s1[i] = (s1[i] - 'a' + last) % SGZ + 'a';
}
last = PTE.query(l, r, s1, len);
printf("%d\n",last);
}
return 0;
}
I am genuinely pleased to glance at this webpage posts which consists of
tons of helpful facts, thanks for providing such statistics.
What i don’t understood is in truth how you are now not really much more well-liked than you might be now.
You’re very intelligent. You recognize thus significantly in terms of
this topic, made me in my view consider it from so
many numerous angles. Its like women and men are not interested until it’s
something to accomplish with Lady gaga! Your own stuffs excellent.
At all times take care of it up!
Valuable information. Lucky me I found your web site by accident, and I’m shocked why this accident did
not happened in advance! I bookmarked it.
I’m extremely inspired together with your writing talents as smartly as with the structure on your blog.
Is this a paid subject matter or did you
modify it your self? Either way keep up the nice quality writing, it is uncommon to see a great weblog
like this one nowadays..
Hi, after reading this remarkable post i am too happy to share my familiarity here with
mates.
Good replies in return of this matter with solid arguments and telling all regarding that.
Excellent goods from you, man. I have take note your stuff prior to
and you are simply too wonderful. I actually like what you’ve bought right here,
really like what you’re saying and the way in which during which you say it.
You make it enjoyable and you continue to take care of to stay it wise.
I can’t wait to read far more from you. That is really
a terrific site.
Simply want to say your article is as surprising.
The clarity in your post is simply cool and i can assume you are an expert on this subject.
Well with your permission let me to grab your feed to keep
up to date with forthcoming post. Thanks a million and please carry on the gratifying
work.
Hi, i feel that i saw you visited my website so
i came to return the desire?.I am attempting to find issues to improve my website!I assume its
good enough to use some of your ideas!!
I just like the valuable info you supply in your articles.
I’ll bookmark your blog and test once more here regularly.
I am rather certain I will be informed a lot of new stuff
right here! Best of luck for the following!
I am regular visitor, how are you everybody? This article
posted at this web site is really pleasant.
Excellent post. I was checking continuously this blog and I am impressed!
Very helpful information specifically the last part 🙂 I care for
such info much. I was seeking this particular information for a long time.
Thank you and good luck.
Whats up this is somewhat of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML.
I’m starting a blog soon but have no coding knowledge so
I wanted to get guidance from someone with experience.
Any help would be greatly appreciated!
This is really interesting, You’re a very skilled blogger.
I’ve joined your rss feed and look forward to seeking more of your great post.
Also, I’ve shared your site in my social networks!
I do not know whether it’s just me or if everyone else experiencing issues with your site.
It appears as if some of the written text on your content
are running off the screen. Can someone else please provide feedback and
let me know if this is happening to them as well?
This may be a problem with my internet browser because I’ve had this happen previously.
Many thanks
Hello would you mind letting me know which webhost you’re working with?
I’ve loaded your blog in 3 different web browsers and I must say this blog
loads a lot quicker then most. Can you recommend a good hosting provider at a honest price?
Cheers, I appreciate it!
Hi there! Do you know if they make any plugins to safeguard against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on.
Any tips?
Every weekend i used to visit this web site, for the reason that
i want enjoyment, since this this web site conations in fact good funny information too.
Howdy just wanted to give you a quick heads up.
The words in your post seem to be running off the screen in Opera.
I’m not sure if this is a format issue or something to do with browser compatibility
but I thought I’d post to let you know. The design look great though!
Hope you get the problem resolved soon. Many thanks
Quality articles or reviews is the secret to be a focus for the users to go to see the
site, that’s what this site is providing.
Hey there, I think your website might be having browser compatibility issues.
When I look at your website in Firefox, 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,
excellent blog!
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 blog and I look forward to seeing
it develop over time. natalielise plenty of fish
I am really glad to glance at this web site posts which
carries plenty of valuable data, thanks
for providing these kinds of statistics.
Hi, i think that i saw you visited my blog so i came to
“return the favor”.I am trying to find things to improve my site!I suppose its
ok to use a few of your ideas!!
I know this site offers quality based posts and extra data,
is there any other web page which provides these kinds of information in quality?
Hi, i think that i saw you visited my site thus i came to “return the favor”.I’m trying to find things to enhance my site!I suppose its ok to use
some of your ideas!!
I’m gone to inform my little brother, that he should also go
to see this blog on regular basis to obtain updated from most recent news.
You are so interesting! I don’t suppose I’ve truly read a single
thing like that before. So nice to find another person with genuine thoughts on this subject.
Seriously.. many thanks for starting this up. This website is something that is
needed on the web, someone with a bit of originality! plenty of fish natalielise
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 throw away your intelligence on just
posting videos to your blog when you could be giving us something enlightening to read?
natalielise plenty of fish
Hi there! Do you know if they make any plugins to protect against hackers?
I’m kinda paranoid about losing everything I’ve worked hard
on. Any recommendations?
Hi i am kavin, its my first occasion to commenting anyplace, when i read
this piece of writing i thought i could also make comment due to this
good paragraph.
Attractive portion of content. I simply stumbled upon your web site and in accession capital to say that
I acquire in fact enjoyed account your blog posts. Any way I
will be subscribing in your augment or even I success you get entry to
consistently fast.
I think the admin of this website is in fact working hard in support of his web
page, for the reason that here every information is quality based information.
Hey this is somewhat of off topic but I was wanting to know
if blogs use WYSIWYG editors or if you have to manually code
with HTML. I’m starting a blog soon but have no coding know-how
so I wanted to get guidance from someone with experience.
Any help would be greatly appreciated!
First of all I want to say excellent blog! I had a quick question that I’d like to
ask if you don’t mind. I was curious to know how you center yourself
and clear your thoughts before writing. I’ve had a
tough time clearing my thoughts in getting my thoughts out.
I do enjoy writing but it just seems like
the first 10 to 15 minutes tend to be wasted just trying to figure out how
to begin. Any suggestions or tips? Cheers!
I used to be able to find good information from your blog posts.
Hi there! This blog post couldn’t be written much better!
Looking through this article reminds me of my
previous roommate! He constantly kept talking about this.
I’ll forward this article to him. Fairly certain he will have a good read.
Thank you for sharing!
I’m really loving the theme/design of your site. Do you ever run into
any browser compatibility problems? A couple of my blog
readers have complained about my website not operating correctly
in Explorer but looks great in Firefox. Do you have any suggestions to
help fix this problem?
I am sure this paragraph has touched all the internet visitors, its really really good piece of writing on building up new website.
I’m not sure exactly why but this blog is loading very slow
for me. Is anyone else having this issue or is it a issue on my end?
I’ll check back later on and see if the problem still exists.
Hmm is anyone else having problems with the images on this blog loading?
I’m trying to find out if its a problem on my end or if it’s the
blog. Any feed-back would be greatly appreciated.
Normally I don’t learn article on blogs, however I wish to say that
this write-up very pressured me to take a look at and do
so! Your writing taste has been amazed me. Thank you, very great post.
If some one wishes expert view concerning running a blog after that i propose him/her to visit this web site,
Keep up the nice job.
I blog quite often and I really appreciate your content.
This great article has really peaked my interest.
I am going to book mark your site and keep checking for new information about once per week.
I opted in for your Feed too.
It’s enormous that you are getting ideas from this paragraph as well as
from our dialogue made at this time.
We absolutely love your blog and find a lot
of your post’s to be precisely what I’m looking for.
Do you offer guest writers to write content available for you?
I wouldn’t mind publishing a post or elaborating on most of
the subjects you write related to here. Again, awesome blog!
Great information. Lucky me I found your blog by chance (stumbleupon).
I have bookmarked it for later!
I have read so many articles or reviews regarding
the blogger lovers but this post is genuinely a pleasant post, keep
it up.
Appreciate the recommendation. Let me try it out.
wonderful post, very informative. I wonder why the opposite specialists of this sector do not
realize this. You must proceed your writing. I’m sure, you’ve a
huge readers’ base already!
Good way of describing, and fastidious post to take facts about my presentation topic, which
i am going to deliver in academy.
My family members all the time say that I am killing my time here at net,
but I know I am getting knowledge everyday by reading such fastidious articles or reviews.
Hello! This is kind of off topic but I need some guidance
from an established blog. Is it difficult to set up your own blog?
I’m not very techincal but I can figure things out pretty fast.
I’m thinking about setting up my own but I’m not sure where to begin. Do you have any
points or suggestions? Cheers
Its like you read my mind! You seem to know
so much about this, like you wrote the book in it or something.
I think that you could do with a few pics to drive the message
home a little bit, but other than that, this is excellent blog.
A great read. I’ll definitely be back.
It’s very straightforward to find out any matter on web as compared to books, as I found
this piece of writing at this website.
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 info. Thanks for the post.
I’ll definitely comeback.
Heya i’m for the primary time here. I came across this board and I in finding It really helpful
& it helped me out a lot. I hope to give something back and help others
such as you aided me.
Hi there, You have done a great job. I will definitely digg it and
personally suggest to my friends. I’m confident they will be benefited from this website.
Aw, this was an incredibly nice post. Taking the time and actual effort to make a great article… but what can I say…
I put things off a whole lot and never seem to get nearly
anything done.
I’m not sure why but this weblog is loading very
slow for me. Is anyone else having this issue or is it a problem on my end?
I’ll check back later and see if the problem still exists.
Great post. I was checking continuously this weblog and I’m inspired!
Extremely helpful information specifically the remaining phase 🙂 I handle such information a
lot. I used to be looking for this particular info
for a very long time. Thank you and good luck.
Wow, awesome weblog layout! How long have
you been blogging for? you made blogging look easy.
The full look of your website is fantastic, let alone the content material!
It’s an remarkable paragraph in favor of all the web visitors; they will
take advantage from it I am sure.
Hey just wanted to give you a quick heads up and let you know a few
of the pictures 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.
I was recommended this web site by my cousin. I am not sure whether this post is written by him as nobody else know such detailed about my trouble. You’re incredible! Thanks!
Hi there friends, how is the whole thing, and what you wish for
to say on the topic of this article, in my view its really amazing designed for me.
Good day I am so glad I found your web site, I really found
you by error, while I was browsing on Yahoo for something else, Anyways I am here now and would just like to say kudos for a fantastic post and a all round thrilling blog (I also love the
theme/design), I don’t have time to look over 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 a lot more, Please do keep up the awesome job.
Wow, awesome weblog layout! How long have you been blogging for?
you made blogging look easy. The entire glance of your
website is great, let alone the content material!
A person essentially help to make critically articles I would
state. This is the first time I frequented your website page and
so far? I surprised with the analysis you made to make this particular submit incredible.
Great activity!
I’m really loving the theme/design of your website.
Do you ever run into any web browser compatibility problems?
A few of my blog audience have complained about my site not working
correctly in Explorer but looks great in Firefox.
Do you have any recommendations to help fix this problem?
Neat blog! Is your theme custom made or did you download it from somewhere?
A theme like yours with a few simple adjustements would really
make my blog shine. Please let me know where you got your design. Thank you
Hey there I am so thrilled I found your web site, I really found you by
mistake, while I was searching on Bing for something else,
Anyways I am here now and would just like to say cheers for a marvelous post
and a all round interesting blog (I also love the theme/design), I don’t
have time to read it all at the minute but I
have book-marked 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 work.
Hurrah! After all I got a weblog from where I
be able to in fact obtain useful facts regarding my study
and knowledge.
Some truly interesting info , well written and generally user genial.
Say, you got a nice post.Really looking forward to read more. Really Cool.