BZOJ3483SGU505Prefixesandsuffixes（询问在线版）Hash，预处理，神做法

Description

GAL发现了N个特殊的字母序列&＃xff0c;由小写字母组成。小L认为&＃xff0c;对于两个字符串s1,s2&＃xff0c;若s1是某个特殊序列的前缀&＃xff0c;s2是该特殊序列的后缀&＃xff0c;则称s1,s2被这个序列拥有。

现在小L给出M对s1,s2&＃xff0c;对于每对字符串&＃xff0c;问它们被几个特殊序列拥有。

Input

第1行一个整数N。

接下来N行&＃xff0c;每行一个字符串&＃xff0c;代表N个特殊序列。

第N&＃43;2行一个整数M。

接下来M行每行一对s1,s2用空格隔开。S1,s2是经过加密的。

设上一问的答案为lastans。解密方法是将s1,s2所有字母向后移动lastans个单位&＃xff0c;这时你要把小写字母表当作一个环&＃xff0c;比如z的下一个字母是a。

Output

对于每次询问操作&＃xff0c;输出一个非负整数表示答案。
Sample Input
3

aaaaa

abacabaa

avtobus

6

a a

y yy

yy y

zzzzz zzzz

zazb bzaz

abac a

Sample Output
2

2

1

1

0

1

HINT

&＃xfeff;设N个特殊序列总长为L1&＃xff0c;所有M组询问总长为L2。L1&＃xff0c;L2<&＃61;2000000.N<&＃61;2000,M<&＃61;100000

解法&＃xff1a; 自己只能写个自然溢出的hash&＃xff0c;但是是ac不了的。看到了一位神牛留下的神奇做法&＃xff0c;对于询问俩串长都小于20的&＃xff0c;可知这种类型有解的情况只有2000*20*20种&＃xff0c;把这些情况预处理答案用map存一下&＃xff0c;然后直接查表&＃xff0c;其余的暴力&＃xff0c;我没有判&＃xff0c;直接全部存了表。。。。然后发现也ac了。。

//BZOJ 3483#include
using namespace std;typedef long long LL;
typedef unsigned long long uLL;
const uLL mod &＃61; 1e9&＃43;7;
const int maxn &＃61; 2010;
int n, m, l[maxn];
string a[maxn];
char ch[2000010];
vector L[maxn], R[maxn];
int ans;void input()
{scanf("%d", &n);for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){scanf("%s", ch);l[i] &＃61; strlen(ch);for(int j &＃61; 0; j for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){last &＃61; 171;for(int j &＃61; 0; j for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){last &＃61; 171;for(int j &＃61; 0; j 1];R[i].push_back(last);}}
}void work()
{scanf("%d", &m);ans &＃61; 0;while(m--){uLL x &＃61; 171, y &＃61; 171;scanf("%s", ch);int len1 &＃61; strlen(ch);for(int j &＃61; 0; j &＃39;a&＃39; &＃43; ans)%26&＃43;&＃39;a&＃39;;for(int j &＃61; 0; j scanf("%s", ch);int len2 &＃61; strlen(ch);for(int j &＃61; 0; j &＃39;a&＃39; &＃43; ans)%26 &＃43; &＃39;a&＃39;;for(int j &＃61; 0; j 1];ans &＃61; 0;for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){if(L[i][len1-1]&＃61;&＃61;x && R[i][len2-1] &＃61;&＃61; y) ans&＃43;&＃43;;}printf("%d\n", ans);}
}void output()
{//printf("%d\n", ans);
}int main()
{input();work();//output();
}