bzoj 4212 神牛的养成计划

内容

Description

Hzwer成功培育出神牛细胞，可最终培育出的生物体却让他大失所望……
后来，他从某同校女神牛处知道，原来他培育的细胞发生了基因突变，原先决定神牛特征的基因序列都被破坏了，神牛hzwer很生气，但他知道基因突变的低频性，说不定还有以下优秀基因没有突变，那么他就可以用限制性核酸内切酶把它们切出来，然后再构建基因表达载体什么的，后面你懂的……
黄学长现在知道了N个细胞的DNA序列，它们是若干个由小写字母组成的字符串。一个优秀的基因是两个字符串s1和s2,当且仅当s1是某序列的前缀的同时，s2是这个序列的后缀时，hzwer认为这个序列拥有这个优秀基因。
现在黄学长知道了M个优秀基因s1和s2，它们想知道对于给定的优秀基因，有多少个细胞的DNA序列拥有它。

Input

第一行：N，表示序列数
接下来N行，每行一个字符串，代表N个DNA序列，它们的总长为L1
接下来一个M，表示询问数
接下来M行，每行两个字符串s1和s2，由一个空格隔开，hzwer希望你能在线回答询问，所以s1等于“s1”的所有字符按字母表的顺序向后移动ans位（字母表是一个环），ans为上一个询问的答案，s2同理。例如ans=2 “s1”=qz
则s1=sb。对于第一个询问，ans=0
s1和s2的总长度为L2

Output

输出M行，每行一个数，第i行的数表示有多少个序列拥有第i个优秀基因。

Sample Input

emikuqihgokuhsywlmqemihhpgijkxdukjfmlqlwrpzgwrwozkmlixyxniutssasrriafu

emikuqihgokuookbqaaoyiorpfdetaeduogebnolonaoehthfaypbeiutssasrriafu

emikuqihgokuorocifwwymkcyqevdtglszfzgycbgnpomvlzppwrigowekufjwiiaxniutssasrriafu

emikuqihgokuorociysgfkzpgnotajcfjctjqgjeeiheqrepbpakmlixyxniutssasrriafu

emikuqihgokuorociysgfrhulymdxsqirjrfbngwszuyibuixyxniutssasrriafu

emikuqihgokuorguowwiozcgjetmyokqdrqxzigohiutssasrriafu

emikuqihgokuorociysgsczejjmlbwhandxqwknutzgdmxtiutssasrriafu

emikuqihgokuorociysgvzfcdxdiwdztolopdnboxfvqzfzxtpecxcbrklvtyxniutssasrriafu

emikuqihgokuorocsbtlyuosppxuzkjafbhsayenxsdmkmlixyxniutssasrriafu

emikuqihgokuorociysgfjvaikktsixmhaasbvnsvmkntgmoygfxypktjxjdkliixyxniutssasrriafu

emikuqihgokuorociysg yxniutssasrriafu

aiegqmedckgqknky eqpoowonnewbq

xfbdnjbazhdnhkhvb qrqgbnmlltlkkbtyn

bjfhrnfedlhrlolzfv qppxpoofxcr

zhdfpldcbjf stsidponnvnmmdvap

zhdfpldcbjfpjmjxdt gdstsidponnvnmmdvap

dlhjtphgfnjtnqnbhxr wxwmhtsrrzrqqhzet

bjfhrnfedlhrlolzfv frqppxpoofxcr

zhdfpldcbjf dponnvnmmdvap

ucyakgyxweakehes nondykjiiqihhyqvk

Sample Output

HINT

N<=2000

L1<=2000000

M<=100000

L2<=2000000

题解

先把所有的串sort一下，让前缀一样的在一个区间里。

然后把这些串正着插到一个Trie树里。每个节点上记下这个点能到的串的l和r(因为sort了所以一定是在一个区间内)

再把这些串倒着插到一个可持久化Trie树里。这样对于询问在Trie里先找这个区间所对应的lr，然后再在可持久化Trie里面匹配下。

#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 2000010
using namespace std;
struct node
{
    int ch[26],val;
}trie[N];
int sz,n,len,cnt,las,root,m,ch[N][26],lc[N],rc[N],roots[N];
char a[N],s[N],s1[N],s2[N];
void insert(int &now,int l,int r)
{
    trie[++sz]=trie[now],trie[sz].val++;now=sz;
    if (l>r) return;
    insert(trie[now].ch[s[r]-'a'],l,r-1);
}
int query(int l,int r,int now)
{
    if (now==-1) return trie[r].val-trie[l].val;
    return query(trie[l].ch[s2[now]-'a'],trie[r].ch[s2[now]-'a'],now-1);
}
struct data
{
    int st,ed;
}dat[2010];
bool comp(data a,data b)
{
    int l=a.st,r=b.st;
    while (l<=a.ed&&r<=b.ed)
    {
        if (s[l]<s[r]) return 1;
        else if (s[l]>s[r]) return 0;
        ++l,++r;
    }
    if (l<=a.ed) return 0;
    else if (r<=b.ed) return 1;
    else return 0;
}
main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
    {
        scanf("%s",a);
        int l=strlen(a);
        dat[i].st=len;
        for (int j=0;j<l;j++)
            s[len++]=a[j];
        dat[i].ed=len-1;
    }
    sort(dat+1,dat+n+1,comp);
    for (int i=1;i<=n;i++)
        for (int now=root,j=dat[i].st;j<=dat[i].ed;j++)
        {
            if (!ch[now][s[j]-'a'])
                ch[now][s[j]-'a']=++cnt;
            now=ch[now][s[j]-'a'];
            if (!lc[now]) lc[now]=i;
            rc[now]=max(rc[now],i);
        }
    for (int i=1;i<=n;i++)
        roots[i]=roots[i-1],
        insert(roots[i],dat[i].st,dat[i].ed);
    scanf("%d",&m);
    for (int i=1;i<=m;++i)
    {
        scanf("%s%s",s1,s2);
        int l1=strlen(s1),l2=strlen(s2);
        for (int j=0;j<l1;j++)
            s1[j]=(s1[j]-'a'+las)%26+'a';
        for (int j=0;j<l2;j++)
            s2[j]=(s2[j]-'a'+las)%26+'a';
        int now=root,l=-1,r=-1;
        for (int j=0;j<l1;j++)
        {
            if (!ch[now][s1[j]-'a'])
                break;
            now=ch[now][s1[j]-'a'];
            if (j==l1-1)
                l=lc[now],r=rc[now];
        }
        if (l==-1&&r==-1)
            las=0,printf("%d\n",las);
        else
            las=query(roots[l-1],roots[r],l2-1),printf("%d\n",las);
    }
}