bzoj 2780 [Spoj]8093 Sevenk Love Oimaster

bzoj 2780 [Spoj]8093 Sevenk Love Oimaster

​​ Description

Oimaster and sevenk love each other.

But recently,sevenk heard that a girl named ChuYuXun was dating with oimaster.As a woman’s nature, s evenk felt angry and began to check oimaster’s online talk with ChuYuXun. Oimaster talked with Ch uYuXun n times, and each online talk actually is a string.Sevenk asks q questions like this, “how many strings in oimaster’s online talk contain this string as their substrings?” 有n个大串和m个询问，每次给出一个字符串s询问在多少个大串中出现过 Input

There are two integers in the first line, the number of strings n and the number of questions q. And n lines follow, each of them is a string describing oimaster’s online talk. And q lines follow, each of them is a question. n<=10000, q<=60000 the total length of n strings<=100000, the total length of q question strings<=360000 Output

For each question, output the answer in one line.

Sample Input

3 3 abcabcabc aaa aafe abc a ca Sample Output

1 3 1 HINT

Source

鸣谢duan2提供译文

将文本串建广义SAM 然后将询问离线

每次询问相当于一棵子树然后 将询问按照子树的结束节点从小到大排序 然后 一边询问一边做 每次做的时候相当于把我这部分改一下 把我的影响改掉 因为我的子树里不可能有我的贡献了同时再把我的贡献加上 即从上一次这个串出现的位置到这次所在的位置都加上1即可 等到我这个询问的子树里的内容都做完了我直接查询我子树开始的位置的值即可

#include#include#include#include#include#includeusing namespace std;const int N=100010;string ss;int ch[N<<1][26],root=1,n,m,last=1,cnt=1,q,len[N<<1],fa[N<<1];vectorc[N<<1];int s[N<<1],lst[N<<1],ans[N];inline void insert1(int x,int id){ int p=last; if(ch[p][x]){ int q=ch[p][x];if (len[p]+1==len[q]){c[q].push_back(id);last=q;return;} int nq=++cnt;memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q];len[nq]=len[p]+1; fa[q]=nq;for (;p&&ch[p][x]==q;p=fa[p]) ch[p][x]=nq;c[nq].push_back(id);last=nq;return; } int np=++cnt;len[np]=len[p]+1;c[np].push_back(id); for (;p&&!ch[p][x];p=fa[p]) ch[p][x]=np; if (!p) fa[np]=root;else{ int q=ch[p][x];if (len[p]+1==len[q]) fa[np]=q;else{ int nq=++cnt;memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q];fa[q]=fa[np]=nq; len[nq]=len[p]+1;for (;p&&ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }last=np;}int top;inline void add(int x,int v){for (;x<=top;x+=x&-x) s[x]+=v;}inline int query(int x){static int tmp;for (tmp=0;x;x-=x&-x) tmp+=s[x];return tmp;}struct node{ int y,next;}data[N<<1];struct node1{int l,r,id;}qr[N];int num,h[N<<1],in[N<<1],out[N<<1],dfn[N<<1];inline bool cmp(const node1 &a,const node1 &b){return a.r>ss;int p=root; for (int i=0;i>n>>q; for (int i=1;i<=n;++i) {cin>>ss;last=root; for (int j=0;j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。