传送门
思路
首先我们甚至不能单独保存每个字符串，因为总长度可以达到
O
(
n
2
)
O(n^2)
O(n2)。于是我们考虑 Trie 树：显然 Trie 树的结点总数是
O
(
n
)
O(n)
O(n) 的。但是建立 Trie 树时显然也不能暴力建树，我们跟随打字机的脚步就可以了，虽然这样会有多的结点，但是总结点数是
O
(
n
)
O(n)
O(n) 的。
现在要询问串
x
x
x 在串
y
y
y 中出现了多少次，我们自然会想到把串
y
y
y 放在 AC 自动机上跑，匹配到
x
x
x 的次数就是答案。这样我们立即得到一个时间复杂度为
O
(
n
m
)
O(nm)
O(nm) 的算法。
我们考虑 AC 自动机的后缀链接树（注：fail 树）。显然，我们看匹配到
x
x
x 的次数的方法是检查从当前结点出发沿着后缀链接树向上走的所有结点有多少
x
x
x。由于
y
y
y 也是在 AC 自动机里的，因此我们要求的就是某条链上所有结点能够到
x
x
x 的个数之和。
我们考虑倒着求：不求某条链上所有结点出发能够到达的
x
x
x 的个数之和，而是求从
x
x
x 出发能够到这条链上多少个结点。在 Trie 树上，我们给当前链上的结点打标记；在后缀链接树上，我们统计
x
x
x 的子树中有多少个有标记的：这个显然可以用树状数组 + DFS 序来完成。
考虑离线，将询问按第一个参数排序，然后照着给出的指令走一次。走到一个结点上时，我们给这个结点打上标记；离开时删除标记。对于某个地方的询问，由于我们的链上是处理好了的，所以我们直接在树状数组里查询第二个参数对应结点在后缀链接树上有多少个打了标记的结点。这样，我们就能在
O
(
n
log
n
)
O(n \log n)
O(nlogn) 的时间复杂度内解决这个问题了。
参考代码
注意各编号的对应关系
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
putchar('\n');
}
const int maxn = int(1e5) + 5;
char origin[maxn];
int n, m, q;
int querys[maxn][2];
int pos[maxn];
int idx[maxn];
bool comp(const int& a, const int& b)
{
return querys[a][1] < querys[b][1];
}
int ans[maxn];
struct Graph
{
struct Edge
{
int to;
int next;
} edges[maxn];
int i;
int head[maxn];
Graph() : i() { memset(head, -1, sizeof(head)); }
void addEdge(int from, int to)
{
edges[i].to = to;
edges[i].next = head[from];
head[from] = i;
i++;
}
#define idx(G) idx_##G
#define wander(G, node) for (int idx(G) = G.head[node]; ~idx(G); idx(G) = G.edges[idx(G)].next)
#define DEF(G) const Graph::Edge& e = G.edges[idx(G)]; int to = e.to
};
struct BIT
{
int bit[maxn];
static inline int lowbit(int x) { return x & -x; }
BIT() : bit() {}
void add(int pos, int val, int size)
{
while (pos <= size)
{
bit[pos] += val;
pos += lowbit(pos);
}
}
int query(int pos)
{
int ret = 0;
while (pos)
{
ret += bit[pos];
pos ^= lowbit(pos);
}
return ret;
}
int query(int l, int r)
{
return query(r) - query(l - 1);
}
};
struct ACAutomaton
{
static const int alphabet = 26;
static inline int code(char ch)
{
return ch - 'a';
}
struct Node
{
int parent;
int ch[alphabet];
int fail;
int suffix;
bool at;
Node() {}
} nodes[maxn];
int size;
void build()
{
size = 1;
int cnt = 0;
for (char* ch = origin; *ch; ch++)
{
if (*ch == 'B')
cnt = nodes[cnt].parent;
else if (*ch == 'P')
{
nodes[cnt].at = true;
pos[++n] = cnt;
}
else
{
int x = code(*ch);
if (!nodes[cnt].ch[x])
{
nodes[cnt].ch[x] = size;
nodes[size++].parent = cnt;
}
cnt = nodes[cnt].ch[x];
}
}
}
void initACAutomaton()
{
static int queue[maxn];
int head = 0, tail = 0;
queue[tail++] = 0;
while (head != tail)
{
int from = queue[head++];
for (int i = 0; i < alphabet; i++)
{
if (int t = nodes[from].ch[i])
{
int temp = nodes[from].fail;
while (temp && !nodes[temp].ch[i])
temp = nodes[temp].fail;
nodes[t].fail = temp = from ? nodes[temp].ch[i] : 0;
nodes[t].suffix = nodes[temp].at ? temp : nodes[temp].suffix;
queue[tail++] = t;
}
}
}
}
Graph G;
void buildGraph()
{
for (int i = 1; i < size; i++)
G.addEdge(nodes[i].suffix, i);
}
int stamp;
void DFS()
{
stamp = 0;
DFS(0);
}
int dfn[maxn];
int end[maxn];
void DFS(int node)
{
dfn[node] = ++stamp;
wander(G, node)
{
DEF(G);
DFS(to);
}
end[node] = stamp;
}
BIT bit;
void query()
{
int cntq = 1;
int cnt = 0;
for (char* ch = origin; *ch; ch++)
{
if (*ch == 'B')
{
bit.add(dfn[cnt], -1, size);
cnt = nodes[cnt].parent;
}
else if (*ch == 'P')
{
while (cntq <= q && pos[querys[idx[cntq]][1]] == cnt)
{
register int t = querys[idx[cntq]][0];
ans[idx[cntq]] = bit.query(dfn[pos[t]], end[pos[t]]);
cntq++;
}
}
else
{
int x = code(*ch);
cnt = nodes[cnt].ch[x];
bit.add(dfn[cnt], 1, size);
}
}
}
} ac;
void run()
{
scanf("%s", origin);
m = strlen(origin);
ac.build();
q = readIn();
for (int i = 1; i <= q; i++)
{
querys[i][0] = readIn();
querys[i][1] = readIn();
}
for (int i = 1; i <= q; i++)
idx[i] = i;
std::sort(idx + 1, idx + 1 + q, comp);
ac.initACAutomaton();
ac.buildGraph();
ac.DFS();
ac.query();
for (int i = 1; i <= q; i++)
printOut(ans[i]);
}
int main()
{
run();
return 0;
}
总结
AC 自动机也有后缀链接树，这道题对统计多个串之间的出现次数有很大的启发。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
