111qqz的小窝

老年咸鱼冲锋!

codeforces 123D. String(后缀自动机)

题目链接:http://codeforces.com/problemset/problem/123/D

题意:

如果字符串y在字符串x中出现n次,那么F(x,y)=n*(n+1)/2

现在给一个字符串,求所有的F(s,x)的和,x为字符串的所有不相同的子串.

思路:

这道题可以考虑用后缀数组做,麻烦一点:codeforces-123D-解题报告(SA)

直接SAM

right[v]就是SAM上状态表示的所有字符串出现的次数。

那么每个状态的答案就是right[v](right[v]+1)/2(st[v].len-st[st[v].link].len)

累加即可。

 

 

poj 3415 Common Substrings (后缀自动机+parent树上的lazy标记)

http://poj.org/problem?id=3415

题意:

给出两个字符串,问公共长度大于等于k的子串个数(只要两个串的位置不同就认为是不同)

思路:

考虑SAM的性质。

SAM上的一个节点所能接受的本质不同的子串个数是st[v].len – st[st[v].link].len

而这些子串,都出现了right[v]次,因为不同子串的个数就是(st[v].len-st[st[v].link].len)*right[v]

现在有了限制条件,要求长度大于等于k.

没有限制的话,SAM上的一个节点所能接受的字符串的长度范围是在[st[st[v].link].len+1,st[v].len]

那么现在范围其实就变成了[MX,st[v].len],其中MX = max{st[st[v].link].len+1,k}

对于A串构建SAM,然后B串在SAM上运行

考虑对于SAM的某个状态,B串此时的最大匹配长度为len,那么len>=MX时,满足条件的字符串的范围就变成了[MX,len] 

len<MX时无贡献。

所以该状态(v)对答案的就是  (len-MX+1)*right[v]

然而这还不算完,和之前的LCS2一样,如果SAM上的一个节点能匹配字符串B的长度大于等于k,那么该节点的祖先节点(父亲节点,父亲的父亲的节点…)

能匹配的字符串B的长度也都大于等于k…

如果我们一边匹配一边沿着parent树自底向上传递的话…复杂度n^2,一首凉凉送给自己

但是正常人会这样?.jpg

我们先打个标记,最后沿parent树自底向上把标记传递上去就行了。。

需要注意的是,此题的字符集是大小写字母都会包含…RE了2发orz

 

hdu 4416 Good Article Good sentence (后缀自动机)

http://acm.hdu.edu.cn/showproblem.php?pid=4416

题意:

给出一个字符串A和n个字符串B,问A的子串中,不在任何一个B中出现的本质不同的子串有多少。

思路:

还是根据len搞事情

我们知道,如果不加任何条件,SAM中一个节点所表示的本质不同的子串数量是st[i].len – st[st[i].link].len

现在加了限制条件。

那么该状态中,有一些长度的字符串就会不满足条件。

我们考虑对母串A构建SAM

那么只需要维护B的所有串,对于某个状态能匹配的最大长度,设为maxlen,那么 长度为[maxlen+1,st[i].len]的字符串可以贡献答案。

如果maxlen为0,则该状态所表示的所有本质不同的子串都可以贡献答案。

维护最大匹配长度 可以参考   spoj-lcs2 解题报告 

有所不同的是不需要在每一个B中都匹配,只需要至少一个匹配就行了,因此是取所有串的最大匹配长度即可。

 

hdu 3518 Boring counting (后缀自动机)

http://acm.hdu.edu.cn/showproblem.php?pid=3518

题意:

给一个字符串,问字符串中,至少出现2次且不相交的本质不同的子串有多少个。本质不同给的子串是说存在至少一位的字母不同。

思路:

考虑SAM

SAM上的一个节点表示的是一段长度从[st[st[i].link],len+1,st[i].len]的字符串。

考虑其right集合,如果right集合中最大的r设为rightmost,最小的r设为leftmost.

那么如果rightmost-leftmost+1 > st[i].len ,说明什么呢?

说明该状态所表示的最长的字符串能够至少放下两个而不重叠。

即从[leftmost-st[i].len+1,leftmost]一段 和 从[rightmost-st[i].len+1,rightmost]一段。

如果最长的能放下,那么其他的也一定能放下。因此对答案贡献为st[i].len – st[st[i].link].len

如果rightmost-leftmost+1<=st[i].len,也就是rightmost-leftmost<st[i].len

这个时候长的字符串因为重叠了不能出现2次,但是短的字符串仍然可以贡献答案。

考虑如下图:

此时对答案的贡献为rightmost-leftmost+1 – (st[st[i].link].len+1),化简得到rightmost-leftmost-st[st[i].link].len

综合2种情况,SAM中每个节点对答案的贡献是 min(rightmost-leftmost,st[i].len)-st[st[i].link].len

需要注意的是只有在st[i].link存在并且rightmost-leftmost>st[st[i].link].len 时 才更新答案

leftmost可以在构建的时候直接求出,rightmost用拓扑序更新下即可。

 

hdu 5558 | 2015ACM/ICPC亚洲区合肥站 G Alice’s Classified Message (后缀自动机)

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=5558

题意:

说了一大堆。。其实就是询问位置i开始的后缀和以位置[0…i – 1]开始的所有后缀中最大匹配的公共前缀长度

思路:

这个动态的过程很容易想到SAM啊。。

所以就一边匹配。。一边构建SAM就好了。。

需要注意的是,如果有多个最长,需要输出最左边的位置。

因此多维护一个leftmost,表示某个字符串第一次出现的结尾的位置。

 

 

 

 

SPOJ LCS2 Longest Common Substring 2[后缀自动机+dp]

题意:

求n个串的最长公共子串,n<=10

思路:

不会啊orz

先放一波参考资料&题解好了。

codeforces_Understanding Suffix Automaton in depth

code风景区_spoj_lcs2

code风景区_sam教学

candy SPOJ 1812 LCS2 [后缀自动机 DP]

 

首先参考下2个串的LCS的做法spoj-lcs

 

卧槽终于懂了…

一个串在上面走的时候记录与每个状态公共子串的最大值,注意出现次数向父亲传递,一个状态能到达说明了Suffix Link指向的状态可以取到最大子串,这一步对val后基数排序然后倒着更新就行了

 

…代码之后补

关键是理解这句话:一个状态能到达说明了Suffix Link指向的状态可以取到最大子串

比如如果状态S(从初始状态到S状态所表示的子串是abcbc) 能够最长向前匹配的长度是x,那么状态s的par的状态Q(从初始状态到Q状态所表示的子串是bc)也至少为x.

所以dp[link[v]] = Max{dp[link[v]],dp[v]}

 

妈个鸡。。。

没事改什么字符集大小啊。。。

上道题做的是数字。。就手贱把字符集的大小改成了12.。。忘了改回来。。WA到死。。。

 

 

hdu 4436 | 2012 Asia Tianjin Regional Contest str2int (dp+后缀自动机,多串建立)

http://acm.hdu.edu.cn/showproblem.php?pid=4436

题意:

给出n个仅由数字组成的字符串,问n个字符串的所有不同子串的和。

思路:

SAM水题

从初始状态开始,走过所有路径,就是该SAM表示的所有的(不重复)子串。

因此只需要从根节点按照拓扑序(这回是根据len从小到大)转移好了。

考虑num[i]表示从SAM中的init状态到i状态能表示的子串的数量。

dp[i]表示从SAM中的init状态到i状态所表示的子串对应的和(也就是到该节点的子串的答案)

那么对于SAM中一个u->v(其中u和v是状态,设转移边为j,j属于0..9)的转移

num[v]+=num[u]

dp[v] = dp[u] * 10 + num[u] * j

初始根节点num[rt]=1,表示唯一的空串。

需要注意,前缀0的数不考虑,所以SAM中 init状态不转移0这条边。

 

SPOJ SUBLEX Lexicographical Substring Search ( 后缀自动机)

http://www.spoj.com/problems/SUBLEX/en/

题意:

给一个字符串,每次询问字典序第k大的不重复子串。

思路:

先做个拓扑dp,求出SAM上,一个状态到种态的路径数。

拓扑dp其实就是按照拓扑序的dp啦…

然后从SAM的初始态开始,每次字典序从小到大得贪心寻找。思想类似可持久化线段树求区间第k大。

 

spoj nsubstr Substrings (后缀自动机 模板题)

http://www.spoj.com/problems/NSUBSTR/en/

题意:

f[i]指长度为i的串出现次数的最大值。这里的不同出现指,可以有重复串,只要起始位置不同就视为不同的出现。

求f[1]..f[lenth]。

思路:

我们知道,SAM上的节点是right集合的等价类。

一个子串的right集合是指在一个母串中,某个子串所有出现位置的右端点的集合。

如果两个子串的right集合完全相同,那么就可以归结为同一个节点,也就是说这两个子串对于SAM是等价的。

因为在SAM上,这两个子串后,添加若干字符得到的后缀都是一样的。

所以一个SAM节点的个数,就是right集合等价类的个数(如果不考虑初始状态)

对于SAM某一个节点,其能表示的子串有一个范围,设为[MIN,MAX]

SAM的一个节点能表示的子串的含义是说,这些子串的right集合相同。

而一个子串出现的次数就是其right集合的大小。

考虑SAM上的某个节点,其表示的长度区间在[MIN,MAX]的子串都出现了|right|次

如果我们直接从MIN更新到MAX有点太暴力了,实际上这里我们可以只更新f[MAX]

由于长度i-1的子串出现的次数一定大于等于长度为i的子串出现的次数,所以最后长度从大到小更新f即可。

现在的问题就变成了如何求right集合。

实际上我们不需要知道right集合的具体组成,只需要知道right集合的大小。

考虑一棵parent树,树上某个节点的right集合就是该节点的所有儿子节点的right集合的并集

因此我们只需要在parent上自低向上更新right集合的大小就可以了。

如何保证在parent树上是自底向上更新呢?

我们只需要按照len,也就是SAM中所有节点能表示的子串的MAX值从大到小的顺序更新right集合。

原因是parent树上,儿子的len一定比父亲的len长。

注意到,对于parent树上的叶子节点,其right集合是1,这也是我们的初始状态。

部分实现细节见代码注释。

关于SAM的详细学习笔记日后补

20171109Update:

注释写错了一处,a[1]应该是len最短的状态的标号,之前写成了最长的。

 

 

 

 

【施工中】SAM学习笔记

*在学习后缀自动机之前需要熟练掌握WA自动机、RE自动机与TLE自动机*

怕是老年人的最后一篇算法学习笔记了

心情不好,此文无限期tj

概述

主要讲解在我学习的过程中比较难理解的地方..并不保证全面

首先,后缀自动机是一个能且只能接受一个字符串的所有后缀的确定性有限状态自动机,也就是DFA

SAM同时具有自动机和树的性质。

节点(状态)

SAM中的节点,也叫状态。

明确一个说法:“一个节点所表示的字符串”。

由于一个字符串的子串一定是某个后缀的前缀。

因此一个字符串的子串一定可以在SAM上运行。

因此“一个节点Q所表示的字符串”的含义是说,从初始状态开始,运行该字符串后,到达的状态是Q.

一个节点所表示的字符串长度属于范围[MIN,MAX],并且区间中每个长度的字符串都出现一次

能表示的字符串长度范围有最大值很好理解,有最小值是因为:长度越小的字符串出现的位置越多,因此当长度小于MIN之后,其出现的位置增加。

由于后文见到,SAM中状态是终点位置集合的等价类,因此一个节点所表示的字符串长度存在一个最小值。

后文还问见到,一个节点的MIN恰好是其父亲节点的MAX+1

终点集合 (endpos / Right)

终点集合一般国内的资料叫right集合,国外好像更常见的叫法是endpos集合。

其实就是对于一个子串a,其在母串S中出现的位置的右端点的集合。

那么这个right集合有什么作用呢?

考虑naive的做法,一个串S有O(n^2)的后缀,凉凉

那么我们发现,对于right集合相同的两个子串,代表其子串的状态(意思是说,从初始状态到该状态所表示的字符串)是可以合并的。

为什么?因为这两个子串的所有出现位置的右端点相同,那么在其后面添加若干字符得到的后缀也一定完全相同。

那么我们可以根据right集合,将字符串的子串分成若干个等价类

对于一个等价类,我们在SAM中用一个状态表示就行了。

接下来考虑right集合的性质。

right[v]表示状态v所表示的子串出现的次数。

 

后缀链/parent树

对于不为初始状态的所有状态,一个状态对应着一个等价类,令w作为其中最长的子串,其余的子串都是w的后缀。

w的所有后缀中,一部分在w所在的等价类中,另外一部分位于其他的等价类中。于是定义后缀链link(v)连接w所有后缀中位于其他等价类并且长度最长的那个后缀所在的等价类。

 

那么根据后缀链的定义,以及后缀的长度是连续的(“后缀的长度是连续的”的含义是说,一个长度为k的字符串,一定有长度为k,为k-1,一直到长度为1的后缀)

因此一个节点的MIN恰好是其父亲节点的MAX+1  (MIN,MAX分别表示一个节点所能表示的字符串的最小值和最大值)

 

复杂度

后缀自动机·张的知乎专栏_震惊!SAM复杂度竟如此显然!

%%%qc大爷

 

构造方法

这个算法是在线的,每次在构造好的自动机的基础上增加一个字符。

对于每个状态,需要保存lenlink以及转移状态信息。

初始条件下,自动机只包含一个起始状态t0len=0并且link指向-1。所有算法要做的就是给后缀自动机增加一个新的字符c。

  • 我们用last来表示当前需要增加一个字符的状态,初始情况下last=0,之后每次增加字符后都会修改。
  • 创建一个新的状态cur,要求len(cur)=len(last)+1link先留着。
  • 接下来进行这样的循环:从last状态开始,如果不存在字符c的转移,那么增加一个到达cur的字符c的转移,然后沿着后缀链继续检查——如果不存在字符串c的转移,那么增加一个转移;如果字符串c的转移已经存在,那么停止循环,将停止时检查的状态记为p。这个时候,会出现两种情况:
    • 如果一直没有遇到存在转移的状态,那么最终我们会到达伪状态-1,只需要让link(cur)=0后退出。
    • 如果遇到存在字符c转移的状态,另q为转移到的状态,那么又有了两种情况:
      • 如果len(p)+1=len(q),只需要令link(cur)=q后退出。
      • 否则,创建一个新的状态clone,将q的转移也拷贝给clone,令len(clone)=len(p)+1。然后,将状态cur和状态q的后缀链指向clone。最后需要完成的事情就是,遍历p的后缀链上的状态,如果存在指向状态q的字符c转移,那么将这个转移重定向到clone(如果不存在,遍历停止)
  • 在任何一种情况下,最后都需要将last设置为cur。

根据后缀链的定义,last开始的后缀链上的状态就是自动机的所有终止状态。

 

 

我的模板

出于太懒的原因,没有封装

需要注意的是,状态数要开到字符串长度的2倍,以及预处理之前先拓扑

需要注意的是,状态数要开到字符串长度的2倍,以及预处理之前先拓扑

需要注意的是,状态数要开到字符串长度的2倍,以及预处理之前先拓扑

 

 

 

 

 

 

 

 

SA&&SAM论文

 SAM学习指南

 

fanhq666_后缀自动机与线性构造后缀树

后缀自动机(SAM)

 

 

 

poj 1509 Glass Beads (后缀自动机求最小循环表示)

 

题意:

给定一个循环字符串,问字典序最小的串的开始位置。

思路:

之前用poj 1509 解题报告-字符串的最小表示法   A过

字符串的最小表示法的复杂度是O(n),代码也不是很难写,不过由于最近在学SAM,所以用SAM写了一下。

参照张天扬的论文:

把原串复制一遍到后面,然后构建后缀自动机。

从初始状态开始,每次走字典序最小的转移,走|S|之后得到的就是最小循环表示。

如果求的是最小后缀,就在原串后加入一个比字符集中所有字符的字典序都小的字符作为终止后,再添加一遍原串。