相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4212
神犇题解：http://www.cnblogs.com/yousiki/p/6550484.html
解题报告
这题如果没有强制在线，那么我们可以用$Trie + bitset$在$O(\frac{2000000n}{64})$的时间复杂度过
如果强制在线并且$s1,s2$等长，那么我们可以在$O(2000000 \log 2000000)$的时间复杂度过
现在解决原问题，先考虑一个暴力：
先把前缀能匹配上的串找出来，然后我们在其中找出后缀能匹配的串
考虑一下后缀数组：按字典序排序后，前缀能匹配上的一定是一个区间
于是我们可以先建一个正串的$Trie$，用来找出前缀合法的字符串区间
然后我们将反串建成一个持久化$Trie$，每一次用前缀合法的区间再去查后缀即可
另外还有一点$Trick$就是字符串排序：我们可以先将正串建成$Trie$，然后贪心$DFS$
这样排序的复杂度就可以是线性的，总的时间复杂度也就是线性的了
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2000009;
const int M = 2009;
const int SGZ = 26;
int n,m,tot,beg[M],sz[M],ord[M];
char s1[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
class Trie{
int cnt,ch[N][26],mn[N],mx[N];
vector<int> id[N];
public:
inline void insert(char *s, int len, int ID) {
int w = 0;
for (int i=0;i<len;i++) {
int c = s[i] - 'a';
if (!ch[w]) ch[w] = ++cnt;
w = ch[w];
}
id[w].push_back(ID);
}
inline void sort(int w, int *arr, int &cur) {
for (int i=0;i<id[w].size();i++) {
arr[++cur] = id[w][i];
}
for (int i=0;i<SGZ;i++) {
if (ch[w][i]) {
sort(ch[w][i], arr, cur);
}
}
}
inline void mark(int val, char *s, int len) {
int w = 0;
for (int i=0;i<len;i++) {
int c = s[i] - 'a';
w = ch[w];
if (!mn[w] || mn[w] > val) mn[w] = val;
if (!mx[w] || mx[w] < val) mx[w] = val;
}
}
inline void query(char *s, int len, int &l, int &r) {
int w = 0;
for (int i=0;i<len;i++) {
int c = s[i] - 'a';
if (!ch[w]) {
l = 1; r = 0;
return;
} else {
w = ch[w];
}
}
l = mn[w];
r = mx[w];
}
private:
}trie;
class Persistent_Trie{
int cnt,root[M],sum[N],ch[N][26];
public:
inline void insert(int p, int w, char *s, int len) {
Insert(root[p], root[w], s, len);
}
inline int query(int l, int r, char *s, int len) {
if (l > r) return 0;
int ret = 0, w = root[r];
for (int i=0;i<len;i++) {
w = ch[w][s[i]-'a'];
}
ret += sum[w];
w = root[l-1];
for (int i=0;i<len;i++) {
w = ch[w][s[i]-'a'];
}
ret -= sum[w];
return ret;
}
private:
void Insert(int p, int &w, char *s, int len) {
w = ++cnt;
sum[w] = sum[p] + 1;
memcpy(ch[w], ch[p], sizeof(ch[w]));
if (len <= 0) return;
int c = s[len-1] - 'a';
Insert(ch[p], ch[w], s, len - 1);
}
}PTE;
int main() {
n = read();
for (int i=1,last=0;i<=n;i++) {
beg[i] = last;
scanf("%s", s1+last);
sz[i] = strlen(s1+last);
trie.insert(s1+last, sz[i], i);
last += sz[i];
}
tot = 0;
trie.sort(0, ord, tot);
for (int i=1;i<=n;i++) {
trie.mark(i, s1+beg[ord[i]], sz[ord[i]]);
PTE.insert(i-1, i, s1+beg[ord[i]], sz[ord[i]]);
}
m = read();
for (int tt=1,last=0,l,r;tt<=m;tt++) {
scanf("%s",s1);
int len = strlen(s1);
for (int i=0;i<len;i++) {
s1[i] = (s1[i] - 'a' + last) % SGZ + 'a';
}
trie.query(s1, len, l, r);
scanf("%s",s1);
len = strlen(s1);
for (int i=0,j=len-1;i<j;i++,j--) {
swap(s1[i], s1[j]);
}
for (int i=0;i<len;i++) {
s1[i] = (s1[i] - 'a' + last) % SGZ + 'a';
}
last = PTE.query(l, r, s1, len);
printf("%d\n",last);
}
return 0;
}
