相关链接
题目传送门: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; }