[CF 316G3]Good Substrings解题报告

题目

Smart Beaver recently got interested in a new word game. The point is as follows: count the number of distinct good substrings of some string
s. To determine if a string is good or not the game uses rules. Overall there are
n rules. Each rule is described by a group of three
(p, l, r), where
p
is a string and l and
r
(l ≤ r) are integers. We’ll say that string
t complies with rule
(p, l, r)
, if the number of occurrences of string
t in string p lies between
l and r, inclusive. For example, string “ab“, complies with rules (“ab“,
1, 2) and (“aab“,
0, 1), but does not comply with rules (“cd“,
1, 2) and (“abab“,
0, 1).

A substring
s[lr]
(1 ≤ l ≤ r ≤ |s|)
of string
s = s1s2
s|s|
(|s| is a length of
s) is string slsl + 1
sr
.

Consider a number of occurrences
of string t in string
p
as a number of pairs of integers l, r
(1 ≤ l ≤ r ≤ |p|) such that
p[lr] = t.

We’ll say that string t is good if it complies with all
n rules. Smart Beaver asks you to help him to write a program that can calculate the number of distinct good substrings of string
s. Two substrings s[x
y]
and s[zw] are cosidered to be distinct iff
s[xy] ≠ s[z
w]
.

Input

The first line contains string
s
. The second line contains integer n. Next
n lines contain the rules, one per line. Each of these lines contains a string and two integers
pi, li, ri, separated by single spaces (0 ≤ li ≤ ri ≤ |pi|).
It is guaranteed that all the given strings are non-empty and only contain lowercase English letters.

The input limits for scoring 30 points are (subproblem G1):

  • 0 ≤ n ≤ 10.
  • The length of string s and the maximum length of string
    p is  ≤ 200.

The input limits for scoring 70 points are (subproblems G1+G2):

  • 0 ≤ n ≤ 10.
  • The length of string s and the maximum length of string
    p is  ≤ 2000.

The input limits for scoring 100 points are (subproblems G1+G2+G3):

  • 0 ≤ n ≤ 10.
  • The length of string s and the maximum length of string
    p is  ≤ 50000.
Output

Print a single integer — the number of good substrings of string
s.


大意就是说:我们给定n个文本串T[1]~T[n]。“好”字符串的定义为:它在第i个文本串中的出现次数在l[i]~r[i]次之间。给一个字符串S,求S有多少个互不相同的好子串。(互不相同是指绝对不同,例如S=”aaa”中,”a”只能算一次)。

题解

官方解法用了后缀数组,不过我们可以用后缀自动机解决。

首先将S和T[1]~T[n]顺序接起来(中间放上分隔符)形成一个新的子串SS:
例如,若S=”aaab”,T[1]=”aa”,T[2]=”aab”,那么SS=”aaab#aa$ab%”(当然实际操作中分隔符不是这样的。有一个小坑:分隔符不能从’z’+1向后顺延,因为这会超出127的范围)。
然后将字符串SS建成后缀自动机MT。

我们可以对MT的每个节点v维护sz[0]~sz[n],其中sz[i]表示v的终点集合中有几个在T[i]中(i=0则为S),如果从初态t0到v的路径上没有分隔符,那sz[i]也就表示节点v所对应的串(们)在T[i]中出现了几次。后缀自动机每次添加非拷贝节点时,其sz数组中只有一个1(取决于当前加的字符在哪个串里)。在建成后缀自动机后,将所有节点按照len排序,然后倒着将每个节点的sz数组加到其后缀链接指向节点的sz数组上。这是后缀自动机中常用的一种DP方式。

有了sz数组后,我们就可以判断每个节点是否对应着“好”字符串。(由于同一节点所对应的字符串们的终点集合相同,所以它们要么都好要么都不好)。

感性地想,我们最后应该是把串S拿到自动机MT上匹配,每一步在到达的节点v处都加上一个什么值。什么值呢?其实是两个:①若v是好节点,加上当前匹配v中串的数目(显然,有可能并未匹配v对应的所有字符串,可能只匹配了长度较短的一部分)。②加上v沿后缀链接能走到的所有好节点的对应字符串数量之和(我们称这个值为suf_sz)。

①便于计算,②可以DP出来,但是!有一个问题:题目让求的是所有不同子串的个数(没错,即使位置不同,只要串一样就算相同)。
怎么办呢?

对自动机中的每个节点记一个值last,含义是它最后一次在S中出现的位置(last=-1代表未在S中出现过)。last值可以像sz数组一样DP出来。最后在MT上跑匹配时,仅当第i次到达的节点v满足v.last=i时,才把v节点的①和②加到答案上。这样实际上就保证了相同的串只在最后一次才会计算。

最后就如前所说,在MT上跑串S的匹配,第i次循环到达节点v时,若v.last=i,则将v节点的①和②加到答案上。

重点关注一下DP,一共有三个:
1.sz数组。初始化为全零。在向MT中添加T[k]中的某个值时,新建节点cur的sz[k]=1.在MT构建完毕后,按照len值倒序遍历所有节点,把它的sz值加到其后缀链接指向的节点的sz上。
2.last值。初始化为-1.在向MT中添加SS[i]时,新建节点cur的last=i。MT构建完毕后,按照len值倒序遍历所有节点,用它的last值更新其后缀链接指向节点的last值。
3.suf_sz。在MT构建完毕后,按照len值顺序遍历所有节点v,将v的后缀链接指向节点的suf_sz加到v的suf_sz上,若后缀链接指向好节点,将其对应的字符串数量加到v的suf_sz上。

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注