UOJ #103. 【APIO2014】Palindromes (回文自动机模板题)

http://uoj.ac/problem/103

题意:

给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s 中出现的次数乘以这个子串的长度。

对于给你的这个字符串 s,求所有回文子串中的最大存在值。

思路:

回文自动机,也叫回文树,但其实并不是树2333,所以以后还是称为回文自动机,缩写为PAM

学会了(?)SAM之后再看PAM真是简单得一逼。

学习笔记之后补。

对于这道题,PAM中一个状态的cnt表示的该状态所表示的回文串出现的次数

len表示的是该状态所表示的回文串的长度

UPDATE:

下面的代码风格太丑了,打算弃用。

更新的代码风格见最后

 

 

 

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到死。。。

 

 

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最短的状态的标号,之前写成了最长的。

 

 

 

 

SPOJ LCS Longest Common Substring (后缀自动机模板题)

题意:

给出2个字符串(2.5E5),问最长公共子串的长度。

思路:

拿一个串建SAM

由于SAM上的任何一个状态,都对应一个或者若干个子串,然后拿另一个串在SAM上面跑就行了

20171110UPdate:我好像说得太简略了。。

参考clj的冬令营讲稿:

  • 给两个长度小于100000的字符串A和B,求出他们的最长公共连续子串。 Ê我们构造出A的后缀自动机SAM
  • 对于SAM的每个状态s,令r为Right(s)中任意的一个元素,它代表的是结束位置在r的,长度在[Min(s),Max(s)]之间的所有子串。
  • 我们不妨对状态s,求出所有B的子串中,从任意r开始往前能匹配的最大长度L,那么min(L,Max(s))就可以更新答案了。
  • 我们考虑用SAM读入字符串B
  • 令当前状态为s,同时最大匹配长度为len Ê我们读入字符x。如果s有标号为x的边,
  • 那么s=trans(s,x),len = len+1 Ê否则我们找到s的第一个祖先a,它有标号为x的边,令
  • s=trans(a,x),len=Max(a)+1。 Ê如果没有这样的祖先,那么令s=root,len=0
  • 在过程中更新状态的最大匹配长度

 

唯一不显然的地方在于,为什么当失配时,我们是沿着parent树向上找。

考虑如下例子:

 

我们知道,parent树,或者叫后缀链树,一个状态S指向的是,总起点开始到S的子串的后缀中,长度最长的后缀,满足该后缀所对应的某个状态Q(对应的意思是说,从初始状态到状态Q表示的子串恰好是该后缀)的right集合和状态S的集合不相等。

 

假设我们目前匹配到的状态表示的子串是abcbc,然后下一位要匹配的字母是b,而状态abcbc没有通过b转移的边(这些图上没有,我懒得画了orz)

这个时候考虑回退…对于abcbc的后缀,bcbc,cbc和abcbc面临的情况是一样的,因为bcbc,cbc,abcbc三个字符串的right集合相同,也就是出现的位置完全相同,那么既然abcbc没有通过b转移的边,bcbc,cbc也一定没有通过b转移的边。

这时候考虑转移到abcbc的par状态,也就是表示子串bc的状态,原因是bc的right集合和abcbc的right集合不同,更准确得说,bc的right集合是包含abcbc的right集合的。

而bc在之前匹配abcbc的时候,已经匹配过了,也就是说bc一定是可以匹配的,

如果此时bc有一条通过b转移的边,此时匹配的长度就变成了bc对应的状态所对应的max再+1

 

 

 

老年人的第一个SAM

关于SAM的笔记之后补。

用了动态的写法.

 

不过还是比较喜欢写静态的?

参考了zqc大爷的代码风格:

 

 

SPOJ CIRUT – CIRU2 (多个圆交,求交任意次的面积,模板题)

题目链接

题意&思路:

给出n个圆

求恰好k个圆相交的面积,k属于1..n

 

先放个别人的代码。。。

我真是体会到了。。。软件工程这门课的重要性。。。

这代码真是烂得印象深刻。。。几何题全是面向过程?

circle和point 类写在一起。。。感觉所有糟糕的写法这份代码全都占了。。。

打算改写一下。。。这代码实在是。。烂得看不下去了。。。

所以说。。。读别人代码。。。才能体会到代码风格的重要性啊。。。orz

重构了代码,感觉清爽了很多。。

 

acdream oj 1124 喵喵的遗憾 (斐波那契数列循环节)

题目链接

题意:

F0 = 1 , F1 = 1 , F2 = 2 , Fn = Fn-1+Fn-2

求:

FFFn Mod P

( 也就是 F[ F[ F[n] ] ]  % P )

思路:原来这是适牛出的题2333.

需要注意的是p可能为1,因此n==0或者1的时候,特判要输出1%p而不是1.

其他的没了。就是求斐波那契数列循环节的经典做法。

 

FZU 2113 Jason的特殊爱好 (数位dp)

题目链接

题意:统计区间[a,b]里数字1出现的次数。

思路:数位dp。

收获是,dfs传递的参数可能是为了判断符合条件的答案(比如不要62中的preis6等)

但是也可能是在统计答案信息。。。pos等于0的时候返回值未必是1和0.。。

然后傻逼fzu。。。long long 必须交 I64d..因为这个wa到死。

傻逼fzu,毁我青春。

 

spoj DQUERY – D-query (询问区间中不同数的个数,线段树(离线) or 莫队算法(离线) or 主席树(在线))

题目链接
题意:给出n个数,然后m个询问,每个询问一个区间[l,r],问该区间中不同的数有多少个。

思路:离线处理+线段树的做法不多说了:

之后补一个主席树的做法

先来补一个莫队的做法。

因为a[i]<=1E6,可以很方便得统计每个数出现的次数,update的时候,如果是1变成0,那么区间中不同的数的个数减1,如果是0变成1,那么区间中不同数个数+1

 

补一个在线的做法,可持久化线段树,其实思路和离线线段树几乎一样。