题解 P4770 【[NOI2018]你的名字】
little_gift
·
·
题解
题意: 给你一个字符串S, 有很多组询问, 每次给定一个T, 求T中不在S[l:r]中出现的本质不同的子串个数.
考虑两件事.
- 在$S$中匹配$T
匹配就是要计算出一个p_i, 表示T[1:i]中在S[l:r]中存在的最长后缀的长度.
或者说, p_i=\max \{x|T[i-x+1:i]\text{在}S[l:r]\text{中出现}\}.
(得出p_i后如何去重在下面可以先看)
如果l = 1, r = |S|.
发现这个过程就是用SAM跑两个字符串最长公共子串的过程.
所以用类似的方法就可以求出每个p_i.
具体地说, 对S建立后缀自动机, 按顺序以T的每一个字符进行转移.
设当前字符为c， 正在S的后缀自动机上的节点p(p初始值为根), 当前匹配长度为l.
如果p存在c这个转移, 那么直接沿转移边走, 并将l加一.
否则沿后缀链接向上跳, 并把l的值更新为后缀链接的len(最长字符串长度), 直到能够转移为止.
现在考虑对于一般的l, r怎么做.
转移时增加一个判断, 只有目标节点所表示的字符串完全包含在S[l:r]中才能够转移.
如何判断? 只要处理出每个节点的right集合(或者其他名字, 只要表示的意义相同), 判断一下right集合中是否有区间内的数即可.
考虑线段树合并, 建立权值线段树表示每个位置是否在right集合中出现.
初始值是每次的last的right集合包含当前处理到的字符的下标(建立后缀自动机的时候传入当前下标然后线段树ins一下即可).
然后拓扑排序(按len排序)/dfs, 将每个节点的所有孩子(后缀链接指向它)的线段树都合并到它自己上.
然后这个操作是不会破坏它孩子的线段树的结构的, 所以全部合并完之后就得到了每个节点的right集合.
因为后缀自动机状态个数线性, 拥有初始值的节点个数也是线性, 所以复杂度是一个\log级别, 可以承受.
但是如果这样的话上面转移需要有一些小变化.
- 查询的时候查询的是right集合中是否存在[L+l, R](L, R是给定的区间, l是当前匹配长度).
- 匹配失败的时候不能直接跳到后缀链接而是要减小l, 这样区间增大, 可能成功匹配(这一步复杂度目测可以优化但是因为复杂度已(hao)经(xiang)对了所以就没写)(事实上如果不判断这个能够拿到96pts(WA\ on\ 21)).
那么现在已经求出了p_i, 如何去重呢?
本质不同的子串……考虑用SAM求.
那么再对每次的T建后缀自动机, 设tot是节点总数, 1表示根节点.
答案就是\sum\limits_{k=2}^{tot}{\max(len[k]-\max(p[minr[k]], len[fa[k]]), 0)}.
~~感性~~理解: 遍历每个节点就是遍历了所有子串, 对于某个节点$k$, 长度不比$p[minr[k]]$大的串是不可行的(至于为什么是$minr$也可以感性理解, 判断后面的匹配长度可能出锅), 长度不比$len[fa[k]]$大的串不在这个节点中. 外面要再取一个$\max$是因为$p[minr[k]]$可能比$len[k]$大.
~~讲的混乱代码也丑……~~
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
namespace Segment_Tree {
const int N = 1000000 * 20;
int rt[N], ls[N], rs[N], tot, n;
inline void init(const int& len) {n = len;}
void ins(int& h, const int& x, const int& l = 1, const int& r = n) {
if (!h) h = ++tot;
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid) ins(ls[h], x, l, mid);
else ins(rs[h], x, mid + 1, r);
}
inline int add(const int& x) {int ret = ++tot; ins(tot, x); return ret;}
int merge(const int& x, const int& y) {
if (!x || !y) return x | y;
int h = ++tot;
ls[h] = merge(ls[x], ls[y]); rs[h] = merge(rs[x], rs[y]);
return h;
}
bool query(const int& h, const int& L, const int& R, const int& l = 1, const int& r = n) {
if (!h || R < l || r < L) return 0;
if (L <= l && r <= R) return 1;
int mid = (l + r) >> 1;
return query(ls[h], L, R, l, mid) | query(rs[h], L, R, mid + 1, r);
}
}
template<int N>
struct Suffix_Automaton {
int len[N], fa[N], minr[N], ch[N][26], rt[N], tot, last;
void clear() {tot = last = 1; memset(ch[1], 0, sizeof(ch[1]));}
Suffix_Automaton() {clear();}
void ins(const int& c, const int& pos = 0) {
int p = last, np = last = ++tot; minr[np] = len[np] = len[p] + 1;
if (pos) rt[np] = ::Segment_Tree::add(pos);
memset(ch[np], 0, sizeof(ch[np]));
for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
if (!p) return void(fa[np] = 1);
int q = ch[p][c];
if (len[p] + 1 == len[q]) return void(fa[np] = q);
int nq = ++tot; len[nq] = len[p] + 1; minr[nq] = minr[q]; fa[nq] = fa[q];
memcpy(ch[nq], ch[q], sizeof(ch[q]));
fa[np] = fa[q] = nq;
for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
}
void find(int& p, int& l, const int& L, const int& R, const int& c) {
while (1) {
if (ch[p][c] && ::Segment_Tree::query(rt[ch[p][c]], L + l, R)) {
++l; p = ch[p][c]; return;
}
if (!l) return;
if (--l == len[fa[p]]) p = fa[p];
}
}
long long calc(int p[]) {
long long ret = 0;
for (register int i = 2; i <= tot; ++i) {
ret += std::max(0, len[i] - std::max(len[fa[i]], p[minr[i]]));
}
return ret;
}
};
Suffix_Automaton<1000001> sam;
Suffix_Automaton<2000001> sam2;
char S[500002], T[1000002];
int p[1000002];
int c[500002], rk[1000002];
int main() {
scanf("%s", S + 1);
int len = strlen(S + 1); Segment_Tree::init(len);
for (register int i = 1; i <= len; ++i) {
sam.ins(S[i] - 'a', i);
}
for (register int i = 1; i <= sam.tot; ++i) ++c[sam.len[i]];
for (register int i = 1; i <= len; ++i) c[i] += c[i - 1];
for (register int i = 1; i <= sam.tot; ++i) rk[--c[sam.len[i]]] = i;
for (register int i = sam.tot; --i; ) {
sam.rt[sam.fa[rk[i]]] = Segment_Tree::merge(sam.rt[sam.fa[rk[i]]], sam.rt[rk[i]]);
}
int Q;
for (scanf("%d", &Q); Q--; ) {
sam2.clear();
int l, r;
scanf("%s%d%d", T + 1, &l, &r);
int _len = strlen(T + 1), _ = 1;
for (register int i = 1; i <= _len; ++i) {
p[i] = p[i - 1];
sam.find(_, p[i], l, r, T[i] - 'a');
sam2.ins(T[i] - 'a');
}
printf("%lld\n", sam2.calc(p));
}
}
```