@loj - 2720@ 「NOI2018」你的名字

悠悠 2023-06-01 13:57 32阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

ION 每年规定一个命名串，要求每道题的名字必须是那一年的命名串的一个非空连续子串，且不能和前一年的任何一道题目的名字相同。  
由于一些特殊的原因，小 A 得到了 ION2017 的命名串。  
现在小 A 有 Q 次询问：每次给定 ION2017 的命名串和 ION2018 的命名串，求有几种题目的命名，使得这个名字是 ION2018 的命名串的一个非空连续子串且一定不会和 ION2017 的任何一道题目的名字相同。  
由于一些特殊原因，所有询问给出的 ION2017 的命名串都是某个串的连续子串。

**输入格式**  
从文件 name.in 读入数据。  
第一行一个字符串 S，之后询问给出的 ION2017 的命名串都是 S 的连续子串。  
第二行一个正整数 Q，表示询问次数。  
接下来 Q 行，每行有一个字符串 T 和两个正整数 l, r，表示询问如果 ION2017 的命名串是 S\[l, r\]，ION2018 的命名串是 T 的话，有几种命名方式一定满足规定。  
保证输入中给出的字符串都是由小写字母构成的。

**输出格式**  
输出到文件 name.out 中。  
输出 Q 行，第 i 行一个非负整数表示第 i 个询问的答案。

**样例输入 1**  
scbamgepe  
3  
smape 2 7  
sbape 3 8  
sgepe 1 9  
**样例输出 1**  
12  
10  
4

**数据范围与提示**  
对于所有数据，保证 1 <= l <= r <= |S| <= 5*10^5, 1 <= |T| <= 5*10^5, ∑|T| <= 10^6, Q <= 10^5。

## @solution@ ##

先考虑 l = 1, r = |S| 的情况。

我们不妨对 S 建出后缀自动机，然后把 T 拿到 S 上跑一跑。对于 T 的每一个前缀 i，我们都求出一个最大的 f\[i\]，使得 T 的前缀 i 的长度为 f\[i\] 的后缀是 S 的子串。  
则显然前缀 i 长度 <= f\[i\] 的所有后缀也在 S 中出现过。

接着我们对 T 建出后缀自动机，然后把每一个前缀对应的结点上打上 f\[i\] 的 tag，然后沿着 parent 树传递 tag。  
这样子就可以处理 T 的后缀自动机中每个结点对应的字符串有多少没有在 S 中出现。于是就可以解决题目的询问。

然后考虑给定的串是 S 的某个子串 S\[l...r\] 时，我们一样是考虑对于每个 i 求出 f\[i\]。  
我们考虑使用可持久化线段树合并，求出 S 的后缀自动机上每一个结点的 end-pos 集合。

则当 T 的前缀 i 匹配上了 S 后缀自动机的结点 x，如果要尽可能在 S\[l...r\] 中匹配成功，我们肯定是选择 end-pos 集合中 <= r 且尽量大的那个。线段树上二分一下即可。  
如果不存在这样一个 end-pos 或是这个 end-pos 对应的字符串超出了左端点，我们就当作匹配失败，继续沿着 parent 树跳。

这样下来，因为要用线段树，所以时间复杂度是 O(|T|\*logn) 的。

## @accepted code@ ##

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 1000000; struct segtree{ struct node{ int ch[2], mx; }pl[20*MAXN + 5]; int ncnt; segtree() {ncnt = 0; pl[0].mx = -1;} void pushup(int x) { if( pl[x].ch[1] ) pl[x].mx = pl[pl[x].ch[1]].mx; else pl[x].mx = pl[pl[x].ch[0]].mx; } int merge(int a, int b) { if( !a ) return b; if( !b ) return a; int c = (++ncnt); pl[c].ch[0] = merge(pl[a].ch[0], pl[b].ch[0]); pl[c].ch[1] = merge(pl[a].ch[1], pl[b].ch[1]); pushup(c); return c; } int insert(int a, int l, int r, int p) { int b = (++ncnt); pl[b].ch[0] = pl[a].ch[0], pl[b].ch[1] = pl[a].ch[1]; if( l == r ) { pl[b].mx = l; return b; } int mid = (l + r) >> 1; if( p <= mid ) pl[b].ch[0] = insert(pl[a].ch[0], l, mid, p); else pl[b].ch[1] = insert(pl[a].ch[1], mid + 1, r, p); pushup(b); return b; } int query(int x, int l, int r, int p) { if( l == r ) return pl[x].mx; int mid = (l + r) >> 1; if( p <= mid ) return query(pl[x].ch[0], l, mid, p); else { int k = query(pl[x].ch[1], mid + 1, r, p); if( k != -1 ) return k; else return pl[pl[x].ch[0]].mx; } } }; struct SAM{ struct node{ node *ch[26], *fa; int mx, pos, tag; }pl[2*MAXN + 5], *lst, *root, *ncnt; SAM() {ncnt = lst = root = &pl[0];} void clear() { int size = ncnt - pl + 1; for(int i=0;i<size;i++) { for(int j=0;j<26;j++) pl[i].ch[j] = NULL; pl[i].fa = NULL, pl[i].mx = pl[i].pos = pl[i].tag = 0; } ncnt = lst = root = &pl[0]; } void extend(int c) { node *cur = (++ncnt), *p = lst; lst = cur; cur->mx = cur->pos = p->mx + 1; while( p && p->ch[c] == NULL ) p->ch[c] = cur, p = p->fa; if( !p ) cur->fa = root; else { node *q = p->ch[c]; if( p->mx + 1 == q->mx ) cur->fa = q; else { node *cne = (++ncnt); (*cne) = (*q); cne->mx = p->mx + 1; cne->pos = 0; cur->fa = q->fa = cne; while( p && p->ch[c] == q ) p->ch[c] = cne, p = p->fa; } } } node *a[2*MAXN + 5]; int b[2*MAXN + 5]; segtree T; int rt[2*MAXN + 5]; void sort(int len) { int size = ncnt - pl + 1; for(int i=1;i<=len;i++) b[i] = 0; for(int i=0;i<size;i++) b[pl[i].mx]++; for(int i=1;i<=len;i++) b[i] += b[i-1]; for(int i=0;i<size;i++) a[--b[pl[i].mx]] = &pl[i]; } void build(int len) { int size = ncnt - pl + 1; sort(len); for(int i=0;i<size;i++) rt[i] = 0; for(int i=size-1;i>0;i--) { if( a[i]->pos ) rt[a[i]-pl] = T.insert(rt[a[i]-pl], 1, len, a[i]->pos); rt[a[i]->fa-pl] = T.merge(rt[a[i]->fa-pl], rt[a[i]-pl]); } } long long solve(int len) { int size = ncnt - pl + 1; sort(len); long long ret = 0; for(int i=size-1;i>0;i--) a[i]->fa->tag = min(a[i]->fa->mx, max(a[i]->fa->tag, a[i]->tag)), ret += max(0, a[i]->mx - max(a[i]->fa->mx, a[i]->tag)); return ret; } void debug(int len) { int size = ncnt - pl + 1; for(int i=0;i<size;i++) { printf("%d : %d %d %d %d\n", i, pl[i].fa-pl, pl[i].mx, pl[i].pos, pl[i].tag); //T.debug(rt[i], 1, len); } puts(""); } }S, T; char str[MAXN + 5]; int mx[MAXN + 5]; int main() { freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); scanf("%s", str); int lenS = strlen(str); for(int i=0;i<lenS;i++) S.extend(str[i] - 'a'); S.build(lenS); int Q; scanf("%d", &Q); for(int i=1;i<=Q;i++) { int l, r, lenT; scanf("%s%d%d", str, &l, &r), lenT = strlen(str); SAM::node *nw = S.root; int tmp = 0, x; for(int j=0;j<lenT;j++) { while( nw && nw->ch[str[j]-'a'] == NULL ) nw = nw->fa; if( nw ) { tmp = min(tmp, nw->mx) + 1, nw = nw->ch[str[j]-'a']; x = S.T.query(S.rt[nw-S.pl], 1, lenS, r); while( nw ) { if( x == -1 ) nw = nw->fa; else { if( nw == S.root || l + nw->fa->mx <= x ) break; else nw = nw->fa; } if( nw ) x = S.T.query(S.rt[nw-S.pl], 1, lenS, r); } if( nw ) tmp = min(tmp, min(x - l + 1, nw->mx)); else tmp = 0, nw = S.root; } else tmp = 0, nw = S.root; mx[j] = tmp; } for(int j=0;j<lenT;j++) T.extend(str[j]-'a'); nw = T.root; for(int j=0;j<lenT;j++) { nw = nw->ch[str[j]-'a']; nw->tag = mx[j]; } printf("%lld\n", T.solve(lenT)); T.clear(); } }

## @details@ ##

因为要对 T 多次建后缀自动机，所以每次询问后要注意清空 T 的后缀自动机。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11361871.html