description

给定𝑛个字符串，有𝑚个询问。
每个询问给出两个字符串𝑠1, 𝑠2，问𝑛个字符串中有多少个字符串满足𝑠1是其前缀，且𝑠2是其后缀。

输入格式
从文件 fix.in 中读入数据。
输入文件的第一行包含一个整数𝑛，含义如上所述。
接下来𝑛行，每行一个字符串。
接下来一行包含一个整数𝑚，代表询问数。
接下来𝑚行,每行包含两个字符串𝑠1, 𝑠2，代表一次询问。询问内容请参见问题描述。
为了体现算法的在线性，我们令上次询问的答案是𝑥（如果这是第一个询问则𝑥 = 0）。询问的两个字符串的所有字符都要按字母表的顺序向后移动𝑥位（字母表是一个环）。例如 x=2，输入的 s1=qz 则查询的 s1=sb。

输出格式
输出到 fix.out 中。
对于每次询问，输出串满足既是𝑠1的前缀，又是𝑠2的后缀的字符串的数量。

样例输入

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

样例输出

数据规模和约定
设𝐿1表示𝑛个字符串的长度之和，𝐿2表示𝑚次查询的字符串𝑠1, 𝑠2的长度之和。

数据点	𝑛的规模	𝑚的规模	L1的规模	L2的规模
1	= 10	= 10	≤ 1000	≤ 500
2	= 200	= 1000	≤ 160000	≤ 160000
3	= 500	= 5000	≤ 400000	≤ 800000
4	= 1000	= 10000	≤ 800000	≤ 400000
5~7	= 2000	= 50000	≤ 1600000	≤ 1600000
8~10	= 2000	= 100000	≤ 1600000	≤ 3200000

对于所有数据，保证字符串的字符集为小写英文字母

solution

刚开始就想了前缀字典树和后缀字典树，但是又要求是同一个字符串，如果暴力存储每个字典树节点代表的子串被包含在哪些字符串里面，似乎就可以前缀后缀对比求出

但这显然会 $T L E$ ，可能跟暴力差不多

害怕空间超限制，我又想到了可持久化字典树，但似乎不大有作用

考试过程中，游老师突然说了句

排完序，就是线性复杂度了

$waitaminute!\rm wait\ a\ minute!$

我好像没有排序诶——我陷入了沉思

排序？？

排什么序？排序为我带来了什么好处吗？？

排序会让序列变得有序~~（废话）~~

树的dfn序，使得树可以被划分成连续区间

$. . . . . .$

真実はいつも一つ！

当我将字符串排序后，对于一段前缀，包含它的字符串一定是一段连续区间！！！

于是乎可以像树的dfn序求节点管辖的子树区间，我可以求出包含该前缀的字符串区间的左右端点

答案通过这一步就进行了字符串筛选，留下的这个区间恰好是所有满足 $s 1$ 是其前缀的字符串

接下来就是进一步筛选，这些字符串中后缀是 $s 2$ 的串

首先我怎么做到只要这一段区间里面的字符串信息呢？？

暴力枚举——这又回到了起点，不可取

是的没错，就是一开始的——可持久化

这样就转化成了前缀和问题， $r$ 版本减去 $l - 1$ 版本即可

$s 2$ 为后缀，似乎也是一开始的——后缀字典树

对，没错，倒着再来一个可持久化字典树

时间复杂度主要是在前缀字典树和后缀字典树上跑 $s 1, s 2$ 长度的字符串求和

前面的一些预处理，复杂度没有超过查询的复杂度

两个部分无交集，复杂度是相加关系

所以取大复杂度而言，的确是线性的

只要想到了，就非常好写这个代码

~~正解其实就是把之前的乱想法，安排了一个顺序，前提是拍好了序而已~~

以上是正解做法

接下来再分享一种方法把

字符串一般都容易想到——哈希

尤其是想不出正解的时候，哈希总归是不会抛弃你的

这道题就是预处理对于每一个字符串的每一个前缀/后缀都哈希一下

一共是 $2 * L 1$ 的

然后查询的时候，就直接枚举 $n$ 个字符串，然后直接调第 $i$ 个字符串长度为 $s 1, s 2$ 的前缀、后缀哈希，跟查询的两个串哈希比较即可

这种做法是 $O (n m)$ 的

code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 2002
#define maxm 1600002
int n, m, len, cnt_pre, cnt_suf;
string s[maxn];
int L[maxm], R[maxm], sum[maxm], root[maxn];
int pre[maxm][26], suf[maxm][26];void insert_pre( int id ) {len = s[id].length();int now = 0;for( int i = 0;i < len;i ++ ) {int k = s[id][i] - 'a';if( ! pre[now][k] ) pre[now][k] = ++ cnt_pre;now = pre[now][k];if( ! L[now] ) L[now] = id;R[now] = id;}
}void insert_suf( int lst, int &now, int id, int d ) {if( ! ~d ) return;now = ++ cnt_suf;for( int i = 0;i < 26;i ++ ) suf[now][i] = suf[lst][i];sum[now] = sum[lst] + 1;int k = s[id][d] - 'a';insert_suf( suf[lst][k], suf[now][k], id, d - 1 );
}string a, b;int find() {int now = 0;for( int i = 0;i < len;i ++ ) {int k = a[i] - 'a';if( ! pre[now][k] ) return 0;else now = pre[now][k];}return now;
}int query( int l, int r, int d ) {int k = b[d] - 'a';if( sum[suf[r][k]] - sum[suf[l][k]] == 0 ) return 0;if( d == 0 ) return sum[suf[r][k]] - sum[suf[l][k]];return query( suf[l][k], suf[r][k], d - 1 );
}int main() {freopen( "fix.in", "r", stdin );freopen( "fix.out", "w", stdout );scanf( "%d", &n );for( int i = 1;i <= n;i ++ ) cin >> s[i];sort( s + 1, s + n + 1 );for( int i = 1;i <= n;i ++ ) insert_pre( i ), insert_suf( root[i - 1], root[i], i, len - 1 );scanf( "%d", &m );int ans = 0;while( m -- ) {cin >> a >> b;len = a.length();for( int i = 0;i < len;i ++ ) {int x = a[i] - 'a';x = ( x + ans ) % 26;a[i] = x + 'a';}int pos = find();if( ! pos ) {printf( "%d\n", ans = 0 );continue;}len = b.length();for( int i = 0;i < len;i ++ ) {int x = b[i] - 'a';x = ( x + ans ) % 26;b[i] = x + 'a';}int l = L[pos], r = R[pos];printf( "%d\n", ans = query( root[l - 1], root[r], len - 1 ) );}return 0;
}