因为我知道后缀自动机的构造是比较难以理解的,所以我想先知道后缀自动机构建出来的东西是什么。

首先后缀自动机构造出来的一定是一个自动机,这个自动机可以接收一个字符串所有的后缀,显然这个自动机是一个DAG图。

然后这个自动机的每个状态代表什么呢?代表结束位置相同的子串,比如ab和aab在aabaab中都在\(3,6\)位置结尾,那么这两个串可以认为在后缀自动机中是同一个状态。

后缀自动机大概维护这么几个东西:

\(MAXLEN[ST]\) : \(ST\)对应的最长的字符串

\(MINLEN[ST]\) : \(ST\)对应的最短的字符串

\(TRANS[ST][]\) : \(ST\)对应的转移函数

\(SLINK[ST]\) : \(ST\)对应的最小的超集,比如\((3,6,9)\)是\((3,6)\)的超集。\(SLINK\)指向的状态一定是当前状态的一个前缀,而且形成的一定是一棵树

\(ENDPOS[ST]\) : \(ST\)状态包含的子串的结束位置个数,可以通过\(SLINK\)树自底向上来求出

至于这个后缀自动机的构造方法,就抄个板子?

http://hihocoder.com/problemset/problem/1445

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。

现在小Hi想知道一部作品中出现了多少不同的旋律?

这个不同旋律出现的次数,对于每个状态,不同的子串个数为\(maxlen-minlen+1\),然后对每个状态算一算就好了。

http://hihocoder.com/problemset/problem/1449

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。

现在小Hi想知道一部作品中所有长度为K的旋律中出现次数最多的旋律的出现次数。但是K不是固定的,小Hi想知道对于所有的K的答案。

通过\(slink\)树,我们可以构建出每个状态的结束位置个数,这样的话就知道了每个\(maxlen\)出现了多少次,因为最后的答案一定是按照长度单调递减的,所以就维护一个类似于前缀最大值就好了。

http://hihocoder.com/problemset/problem/1457

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。

神奇的是小Hi发现了一部名字叫《十进制进行曲大全》的作品集,顾名思义,这部作品集里有许多作品,但是所有的作品有一个共同特征:只用了十个音符,所有的音符都表示成0-9的数字。

现在小Hi想知道这部作品中所有不同的旋律的“和”(也就是把串看成数字,在十进制下的求和,允许有前导0)。答案有可能很大,我们需要对(10^9 + 7)取摸。

用像后缀数组处理多串的方法,把所有的串都串起来,然后在DAG跑个DP套DP就好了。

http://hihocoder.com/problemset/problem/1465

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。

小Hi发现旋律可以循环,每次把一段旋律里面最前面一个音换到最后面就成为了原旋律的“循环相似旋律”,还可以对“循环相似旋律”进行相同的变换能继续得到原串的“循环相似旋律”。

小Hi对此产生了浓厚的兴趣,他有若干段旋律,和一部音乐作品。对于每一段旋律,他想知道有多少在音乐作品中的子串(重复便多次计)和该旋律是“循环相似旋律”。

对于循环同构的一个处理方法就是把字符串翻倍,然后看看最长公共子串是不是大于\(N\),问题就是怎么求这个最长公共子串。

我们用类似kmp的方法处理,然后用endpos记一下数,就好了。

发表评论

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