题面

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

10

emikuqihgokuhsywlmqemihhpgijkxdukjfmlqlwrpzgwrwozkmlixyxniutssasrriafu

emikuqihgokuookbqaaoyiorpfdetaeduogebnolonaoehthfaypbeiutssasrriafu

emikuqihgokuorocifwwymkcyqevdtglszfzgycbgnpomvlzppwrigowekufjwiiaxniutssasrriafu

emikuqihgokuorociysgfkzpgnotajcfjctjqgjeeiheqrepbpakmlixyxniutssasrriafu

emikuqihgokuorociysgfrhulymdxsqirjrfbngwszuyibuixyxniutssasrriafu

emikuqihgokuorguowwiozcgjetmyokqdrqxzigohiutssasrriafu

emikuqihgokuorociysgsczejjmlbwhandxqwknutzgdmxtiutssasrriafu

emikuqihgokuorociysgvzfcdxdiwdztolopdnboxfvqzfzxtpecxcbrklvtyxniutssasrriafu

emikuqihgokuorocsbtlyuosppxuzkjafbhsayenxsdmkmlixyxniutssasrriafu

emikuqihgokuorociysgfjvaikktsixmhaasbvnsvmkntgmoygfxypktjxjdkliixyxniutssasrriafu

10

emikuqihgokuorociysg yxniutssasrriafu

aiegqmedckgqknky eqpoowonnewbq

xfbdnjbazhdnhkhvb qrqgbnmlltlkkbtyn

bjfhrnfedlhrlolzfv qppxpoofxcr

zhdfpldcbjf stsidponnvnmmdvap

zhdfpldcbjfpjmjxdt gdstsidponnvnmmdvap

dlhjtphgfnjtnqnbhxr wxwmhtsrrzrqqhzet

bjfhrnfedlhrlolzfv frqppxpoofxcr

zhdfpldcbjf dponnvnmmdvap

ucyakgyxweakehes nondykjiiqihhyqvk

Sample Output

4

7

3

5

5

1

3

5

10

4

Hint

N<=2000

L1<=2000000

M<=100000

L2<=2000000

题解

有一个很简单的思路：假设以

S

1

S_1

S1​ 为前缀的串集合为

A

A

A ，以

S

2

S_2

S2​ 为后缀的串集合为

B

B

B ，我们求

∣

A

∩

B

∣

|A\cap B|

∣A∩B∣.

那么，实践起来，就是字典树统计前缀后缀，字典树上用bitset维护集合。

这样的时间复杂度是

O

(

L

n

64

)

O(L\frac{n}{64})

O(L64n​) ，但是每个节点开个 bitset 空间会炸。

我们再想，该字典树有什么性质？

——只有

O

(

n

)

O(n)

O(n) 个叶子

因为一条无分叉的链上，bitset一定相等，所以，最终整棵树上本质不同的 bitset 最多有

2

n

−

1

2n-1

2n−1 个。

我们把一条无分叉链上的 bitset 只存一个，只保留最靠近叶子的那个，其余节点用一个指针指向那一个 bitset ，就可以省下大把空间。

CODE

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<ctime>

#include<queue>

#include<bitset>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 3200005

#define LL long long

#define ULL unsigned long long

#define UI unsigned int

#define DB double

#define ENDL putchar('\n')

#define lowbit(x) (-(x) & (x))

#define FI first

#define SE second

#define eps (1e-4)

#define SI(x) set<x>::iterator

#define MI map<int,int>::iterator

#define BI bitset<2002>

LL read() {

	LL f=1,x=0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f*x;

}

void putpos(LL x) {

	if(!x) return ;

	putpos(x/10); putchar('0'+(x%10));

}

void putnum(LL x) {

	if(!x) putchar('0');

	else if(x < 0) putchar('-'),putpos(-x);

	else putpos(x);

}

void AIput(LL x,char c) {putnum(x);putchar(c);}

int n,m,s,o,k;

BI b[100005];

int tre[MAXN][26],to[MAXN],cnt = 2,cnb;

void ins(int p,char *s,int n,int id) {

	for(int i = 1;i <= n;i ++) {

		int d = s[i]-'a';

		if(!tre[p][d]) tre[p][d] = ++ cnt;

		p = tre[p][d];

	}

	if(!to[p]) {

		int t = ++ cnb;

		b[t][id] = 1;

		to[p] = t;

	}

	else {

		b[to[p]][id] = 1;

	}return ;

}

void dfs(int p) {

	if(!p) return ;

	int sm = 0,t = 0;

	if(to[p]) sm = 1,t = to[p];

	for(int i = 0;i < 26;i ++) {

		if(tre[p][i]) {

			dfs(tre[p][i]);

			sm ++;

			if(sm == 1) t = to[tre[p][i]];

			else if(sm == 2) {

				b[++ cnb] = b[t] | b[to[tre[p][i]]];

				t = cnb;

			}

			else {

				b[t] |= b[to[tre[p][i]]];

			}

		}

	}

	to[p] = t;

	return ;

}

int query(int p,char *s,int n) {

	for(int i = 1;i <= n;i ++) {

		int d = s[i]-'a';

		if(!tre[p][d]) return 0;

		p = tre[p][d];

	}return to[p];

}

char ss[MAXN],s1[MAXN],s2[MAXN];

int main() {

	n = read();

	for(int i = 1;i <= n;i ++) {

		scanf("%s",ss + 1);

		m = strlen(ss + 1);

		ins(1,ss,m,i);

		for(int j = 1;j*2 <= m;j ++) swap(ss[j],ss[m-j+1]);

		ins(2,ss,m,i);

	}

	dfs(1);dfs(2);

	m = read();

	int las = 0;

	while(m --) {

		scanf("%s",s1 + 1);

		scanf("%s",s2 + 1);

		s = strlen(s1 + 1);

		o = strlen(s2 + 1);

		for(int i = 1;i <= s;i ++) s1[i] = (s1[i]-'a'+las) % 26 + 'a';

		for(int i = 1;i <= o;i ++) s2[i] = (s2[i]-'a'+las) % 26 + 'a';

		for(int i = 1;i*2 <= o;i ++) {

			swap(s2[i],s2[o-i+1]);

		}

		BI as = b[query(1,s1,s)] & b[query(2,s2,o)];

		las = as.count();

		AIput(las,'\n');

	}

	return 0;

}

BZOJ4212 神牛的养成计划 （字典树，bitset）的相关教程结束。