题面
Description
Tom有n个字符串S1,S2...Sn，Jerry有一个字符串集合T，一开始集合是空的。
接下来会发生q个操作，操作有两种形式：
“1 P”，Jerry往自己的集合里添加了一个字符串P。
“2 x”，Tom询问Jerry，集合T中有多少个字符串包含串Sx。（我们称串A包含串B，当且仅当B是A的子串）
Jerry遇到了困难，需要你的帮助。
Input
第1行，一个数n；
接下来n行，每行一个字符串表示Si；
下一行，一个数q；
接下来q行，每行一个操作，格式见题目描述。
Output
对于每一个Tom的询问，帮Jerry输出答案。
Sample Input
3
a
bc
abc
5
1 abca
2 1
1 bca
2 2
2 3
Sample Output
1
2
1
HINT
100%: \(1≤N,Q≤100000\), \(\sum_{s \in S} |s|, \sum_{s \in T}|s| \le 2 \times 10^6\), \(alphabet = \{a ... z\}\)
Solution
正解貌似是fail树加树链的并, 但我写的是后缀树. 还没读入完空间就炸了... 先放一份代码吧
#include <cstdio>
#include <cstring>
#include <vector>
#define vector std::vector
const int LEN = (int)2e6, N = (int)1e5, Q = (int)1e5;
int q;
int ans[Q];
struct segmentTree
{
struct node
{
node *suc[2];
int sz;
inline node() {for(int i = 0; i < 2; ++ i) suc[i] = NULL; sz = 0;}
}*rt;
inline segmentTree() {rt = NULL;}
node* insert(node *u, int L, int R, int pos)
{
if(u == NULL) u = new node;
if(L == R) {u->sz = 1; return u;}
if(pos <= L + R >> 1) u->suc[0] = insert(u->suc[0], L, L + R >> 1, pos); else u->suc[1] = insert(u->suc[1], (L + R >> 1) + 1, R, pos);
u->sz = 0;
for(int i = 0; i < 2; ++ i) if(u->suc[i] != NULL) u->sz += u->suc[i]->sz;
return u;
}
inline void insert(int pos) {rt = insert(rt, 1, q, pos);}
int query(node *u, int L, int R, int pos)
{
if(u == NULL) return 0;
if(R <= pos) return u->sz;
return query(u->suc[0], L, L + R >> 1, pos) + (pos > L + R >> 1 ? query(u->suc[1], (L + R >> 1) + 1, R, pos) : 0);
}
inline int query(int pos) {return query(rt, 1, q, pos);}
node* merge(int L, int R, node *u, node *_u)
{
if(u == NULL) return _u; if(_u == NULL) return u;
if(L == R) {u->sz |= _u->sz; delete _u; return u;}
u->suc[0] = merge(L, L + R >> 1, u->suc[0], _u->suc[0]); u->suc[1] = merge((L + R >> 1) + 1, R, u->suc[1], _u->suc[1]);
delete _u;
u->sz = 0;
for(int i = 0; i < 2; ++ i) if(u->suc[i] != NULL) u->sz += u->suc[i]->sz;
return u;
}
inline void merge(segmentTree *T) {rt = merge(1, q, rt, T->rt);}
};
struct suffixAutomaton
{
struct node
{
node *suc[26], *pre;
int len;
vector<int> bck, qry;
int vst;
vector<node*> successorOnSuffixTree;
inline node() {for(int i = 0; i < 26; ++ i) suc[i] = NULL; pre = NULL; vst = 0; bck.clear(); qry.clear(); successorOnSuffixTree.clear();}
}*rt;
inline suffixAutomaton() {rt = new node; rt->len = 0;}
inline node* insert(char *str, int len, int id)
{
node *lst = rt;
for(int i = 0; i < len; ++ i)
{
int c = str[i] - 'a';
if(lst->suc[c] != NULL)
{
node *p = lst->suc[c];
if(p->len == lst->len + 1) { if(~ id) p->bck.push_back(id); lst = p; continue;}
node *q = new node; if(~ id) q->bck.push_back(id);
for(int i = 0; i < 26; ++ i) q->suc[i] = p->suc[i]; q->pre = p->pre; q->len = lst->len + 1;
p->pre = q;
for(; lst != NULL && lst->suc[c] == p; lst = lst->pre) lst->suc[c] = q;
lst = q;
continue;
}
node *u = new node; u->len = lst->len + 1; if(~ id) u->bck.push_back(id);
for(; lst != NULL && lst->suc[c] == NULL; lst = lst->pre) lst->suc[c] = u;
if(lst == NULL) u->pre = rt;
else
{
node *p = lst->suc[c];
if(p->len == lst->len + 1) u->pre = p;
else
{
node *q = new node; for(int i = 0; i < 26; ++ i) q->suc[i] = p->suc[i]; q->pre = p->pre; q->len = lst->len + 1;
u->pre = p->pre = q;
for(; lst != NULL && lst->suc[c] == p; lst = lst->pre) lst->suc[c] = q;
}
}
lst = u;
}
return lst;
}
void build(node *u)
{
u->vst = 1; if(u->pre != NULL) u->pre->successorOnSuffixTree.push_back(u);
for(int i = 0; i < 26; ++ i) if(u->suc[i] != NULL && ! u->suc[i]->vst) build(u->suc[i]);
}
inline void buildSuffixTree() {build(rt);}
segmentTree* DFS(node *u)
{
segmentTree *seg = new segmentTree;
for(auto id : u->bck) seg->insert(id);
for(auto v : u->successorOnSuffixTree)
{
segmentTree *res = DFS(v);
seg->merge(res);
}
for(auto qry : u->qry) ans[qry] = seg->query(qry);
return seg;
}
inline void work() {DFS(rt);}
}SAM;
int main()
{
#ifndef ONLINE_JUDGE
freopen("davljak.in", "r", stdin);
freopen("davljak.out", "w", stdout);
#endif
int n; scanf("%d\n", &n);
static char str[LEN];
static suffixAutomaton::node *ed[N + 1];
for(int i = 1; i <= n; ++ i) scanf("%s", str), ed[i] = SAM.insert(str, strlen(str), -1);
scanf("%d", &q);
for(int i = 1; i <= q; ++ i)
{
int opt; scanf("%d ", &opt);
if(opt == 1) scanf("%s", str), SAM.insert(str, strlen(str), i);
else if(opt == 2)
{
int x; scanf("%d", &x);
ed[x]->qry.push_back(i);
}
}
SAM.buildSuffixTree();
memset(ans, -1, sizeof(ans));
SAM.work();
for(int i = 1; i <= q; ++ i) if(~ ans[i]) printf("%d\n", ans[i]);
}