有 n 个字符串 S[1],S[2],...,S[n], 一个字符串集合 T, 初始为空. q 个操作: - 往 T 中添加字符串 P - S[x] 是 T 中多少个元素的子串?
(1 ≤ n,q ≤ 10^5, Σ|S[i]|, Σ|P| ≤ 2*10^6)
一道差不多的题: [bzoj 2754] [SCOI2012]喵星球上的点名 注意, 问的是 T 中有多少个字符串包含 S[x], 而不是 S[x] 在 T 中的字符串里出现了多少次......
建出 S 的 AC 自动机和 fail 树, 问题转化为: 树上每个点有一个集合, 支持 - 向某集合添加一个元素 (时间戳) - 询问某子树中所有集合的并的大小
| 算法一 离线 + 线段树合并 |
| 线段树维护每个点的集合, 自底向上合并. 查询线段树内 [1,m] 的元素个数 (m 是询问的时间). |
但是要卡一卡空间......手段包括但不仅限于: - AC 自动机用 map 来存边 (无法把转移补全, 多了几行代码) - 用 (非递归式) 拓扑排序代替 DFS, 省下邻接表和递归栈 |
| 写到这里才发现我的线段树数组开大了...... O(L lg q) 弄成了 O(L lg L). 那么应该不用卡空间. 但是栈溢出还是有可能出现的, 所以仍然建议避免 DFS. |
| 然后就可以 AC 了. 设字符串总长为 L, 时间复杂度 O(L lg |Σ| + (L+q) lg q), 空间复杂度 O(L lg q). |
| 一个优化: 对单词节点建虚树, 则 fail 树的规模减至 O(n). |
算法二 LCA + 树链的并 (在线)
上面在线段树合并的时候做处理, 以避免重复. 因为集合中的元素实际上是时间戳, 所以总是一次性加完一种元素. 对涉及到的所有点建虚树, 我们可以清清楚楚地看到哪些子树的答案发生了变化. 树链剖分? 做一个小小的转化: 链修改/点查询 -> 点修改/子树查询. 一个 BIT 即可.
不必把虚树建出来. 按先序遍历的 DFS 序给点排序, 所有点 +1, 相邻两点的 LCA -1.
| 算法三 LCT + 树链的并 (在线) [BZOJ3881][Coci2015]Divljak - Trinkle的日志 |
| 排序后对每个点依次 access, 我们就求出了树链的并. 直接修改即可. |
bzoj 2754 还要统计 T 中每个元素包含 S 中多少个作为子串. 树上前缀和, 数一数树链的并中有多少个单词节点. 此时算法一就不太好搞了......
算法一的代码
typedef pair<int, int> ii;
const int L = 2e6 + 2, SIGMA = 26, N = 1e5, L_LG_Q = 18*L;
struct SegmentTree
{
int ptr, root[L], lc[L_LG_Q], rc[L_LG_Q], v[L_LG_Q];
void merge(int& x, int y, int l, int r)
{
if (!x || !y)
{
if (!x) x = y;
}
else if (l == r)
{
v[x] = v[x] || v[y];
}
else
{
int m = (l+r)/2;
merge(lc[x], lc[y], l, m);
merge(rc[x], rc[y], m+1, r);
v[x] = v[lc[x]] + v[rc[x]];
}
}
void build(int& x, int l, int r, int t)
{
v[x = ++ptr] = 1;
if (l == r) return;
int m = (l+r)/2;
if (t <= m) build(lc[x], l, m, t);
else build(rc[x], m+1, r, t);
}
int query(int L, int R, int x, int l, int r)
{
if (!x) return 0;
if (L <= l && r <= R) return v[x];
int m = (l+r)/2, s = 0;
if (L <= m) s = query(L, R, lc[x], l, m);
if (R > m) s += query(L, R, rc[x], m+1, r);
return s;
}
} T;
int q, f[L], d[L];
struct ACautomaton
{
int ptr;
map<char, int> ch[L];
typedef map<char, int>::iterator iter;
ACautomaton(): ptr(1) {}
int insert(char* s)
{
int x = 1;
while (*s)
{
char i = *s++;
if (!ch[x].count(i)) ch[x].insert(make_pair(i, ++ptr));
x = ch[x][i];
}
return x;
}
void build()
{
queue<int> Q;
Q.push(1);
while (!Q.empty())
{
int x = Q.front(); Q.pop();
for (iter it = ch[x].begin(); it != ch[x].end(); ++it)
{
char i = it->first;
int y = it->second, z = f[x];
while (z && !ch[z].count(i)) z = f[z];
++d[f[y] = z ? ch[z][i] : 1];
Q.push(y);
}
}
}
void add(char* s, int t)
{
int x = 1;
while (*s)
{
char i = *s++;
while (x && !ch[x].count(i)) x = f[x];
x = x ? ch[x][i] : 1;
if (x != 1)
{
int tmp;
T.build(tmp, 1, q, t);
T.merge(T.root[x], tmp, 1, q);
}
}
}
} ac;
int top, seq[L], pos[N], ans[N];
vector<ii> Q[L];
void solve(int x)
{
rep (i, 0, Q[x].size())
{
int k = Q[x][i].first, t = Q[x][i].second;
ans[k] = T.query(1, t, T.root[x], 1, q);
}
T.merge(T.root[f[x]], T.root[x], 1, q);
}
char s[L];
int main()
{
int n, m = 0, o;
scanf("%d", &n);
rep (i, 0, n) scanf("%s", s), pos[i] = ac.insert(s);
ac.build();
scanf("%d", &q);
memset(ans, -1, sizeof(int)*q);
rep (i, 0, q)
{
scanf("%d", &o);
if (o == 1)
{
scanf("%s", s);
ac.add(s, ++m);
}
else
{
scanf("%d", &o);
if (m) Q[pos[o-1]].push_back(ii(i, m));
else ans[i] = 0;
}
}
rep (i, 1, ac.ptr+1) if (!d[i]) seq[top++] = i;
while (top)
{
int x = seq[--top];
solve(x);
if (!--d[f[x]]) seq[top++] = f[x];
}
rep (i, 0, q) if (ans[i] >= 0) printf("%d\n", ans[i]);
return 0;
}