题目背景

实力强大的小A 被选为了 ION2018 的出题人,现在他需要解决题目的命名问题。

题目描述

小A 被选为了 ION2018 的出题人,他精心准备了一道质量十分高的题目,且已经把除了题目命名以外的工作都做好了。

由于 ION 已经举办了很多届,所以在题目命名上也是有规定的, ION 命题手册规定:每年由命题委员会规定一个小写字母字符串,我们称之为那一年的命名串,要求每道题的名字必须是那一年的命名串的一个非空连续子串,且不能和前一年的任何一道题目的名字相同。

由于一些特殊的原因,小A 不知道 ION2017 每道题的名字,但是他通过一些特殊手段得到了 ION2017 的命名串,现在小A 有 Q 次询问:每次给定 ION2017 的命名串和 ION2018 的命名串,求有几种题目的命名,使得这个名字一定满足命题委员会的规定,即是 ION2018 的命名串的一个非空连续子串且一定不会和 ION2017 的任何一道题目的名字相同。

由于一些特殊原因,所有询问给出的 ION2017 的命名串都是某个串的连续子串,详细可见输入格式。

输入和输出

输入格式

第一行一个字符串 S,之后询问给出的 ION2017 的命名串都是 S 的连续子串。 第二行一个正整数 Q,表示询问次数。 接下来 Q 行,每行有一个字符串 T 和两个正整数 $l,r$,表示询问如果 ION2017 的 命名串是 $S [l..r]$, ION2018 的命名串是 T 的话,有几种命名方式一定满足规定。

输出格式

输出Q 行,第 i 行一个非负整数表示第 i 个询问的答案。

样例

输入

输出

数据范围和提示

测试点 $∣S∣≤$ $Q≤$ $∑∣T∣≤$ 其他限制
1 $200$ $200$ $40000$ $∣T∣≤200$
2 $1000$ $200$ $40000$ $∣T∣≤200$
3 $1000$ $200$ $40000$ $∣T∣≤200$
4 $1000$ $200$ $5×10^5$
5 $1000$ $200$ $5×10^5$
6 $5×10^5$ $1$ $5×10^5$
7 $5×10^5$ $1$ $5×10^5$
8 $10^5$ $10^5$ $2×10^5$
9 $10^5$ $10^5$ $2×10^5$ 字符串随机
10 $2×10^5$ $10^5$ $4×10^5$
11 $2×10^5$ $10^5$ $4×10^5$ 字符串随机
12 $3×10^5$ $10^5$ $6×10^5$
13 $3×10^5$ $10^5$ $6×10^5$ 字符串随机
14 $4×10^5$ $10^5$ $8×10^5$
15 $4×10^5$ $10^5$ $8×10^5$ 字符串随机
16 $5×10^5$ $10^5$ $10^6$
17 $5×10^5$ $10^5$ $10^6$ 字符串随机
18 $2×10^5$ $10^5$ $10^6$
19 $3×10^5$ $10^5$ $10^6$
20 $4×10^5$ $10^5$ $10^6$
21 $5×10^5$ $10^5$ $10^6$
22 $5×10^5$ $10^5$ $10^6$
23 $5×10^5$ $10^5$ $10^6$
24 $5×10^5$ $10^5$ $10^6$
25 $5×10^5$ $10^5$ $10^6$

思路

我们考虑求 $T$ 的一个前缀在 $S[l,r]$ 中能匹配的最长后缀。

首先我们需要对$T$和$S$分别建立 SAM,然后我们考虑对 $T$ 的一个前缀不断加入新字符。在 $S$ 的 parent 树里,如果当前状态存在一条到新插入字符的边,新状态合法,就说明新状态在 parent 树的子树中存在至少一个前缀结点,其深度在 $[l+l’,r]$ 之间。

所以我们只需要再用主席树对 DFS序 维护一下深度即可。

答案计数到 i 的时候的 $max(0,dep[i]-max(dep[fa[i]],lim))$ 也很好理解了是不是哇。

╰( ̄ω ̄o)

代码

  1. oyyj603470138
    Aug 21, 2018

    讲线段树合并

    Reply
  2. oyyj603470138
    Aug 21, 2018

    解释一下为什么您的SAM这么长?
    看不懂

    Reply
    • xgzepto
      Aug 21, 2018

      我也看不懂🙃

      Reply
  3. DOFY
    Jul 28, 2018

    神仙

    Reply
    • xgzepto
      Jul 30, 2018

      哦 ヾ(o・ω・)ノ

      Reply
  4. hodpel
    Jul 26, 2018

    话说是不是时间不对 显示的是下午9:41… 话说 苹果好像很喜欢这个时间2333

    Reply
    • xgzepto
      Jul 26, 2018

      蛤。。。

      Reply
  5. hodpel
    Jul 25, 2018

    文末没了….

    Reply
    • xgzepto
      Jul 25, 2018

      刚刚更新,依然没写完。

      Reply