题目链接：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) 累加即可。 /* …

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] 那么现在范围其实就变成 …

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，则该状态所表 …

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 ，说明什么呢？ 说明该状态所表示的最长的字符串能够至少放下两个而不重叠。 即 …

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=5558 题意： 说了一大堆。。其实就是询问位置i开始的后缀和以位置[0...i - 1]开始的所有后缀中最大匹配的公共前缀长度 思路： 这个动态的过程很容易想到SAM啊。。 所以就一边匹配。。一边构建SAM就好了。。 需要注意的是，如果有多个最长，需要输出最左边的位置。 因此多维护一个leftmost,表示某个字符串第一次出现的结尾的位置。 /* *********************************************** Author :111qqz Created Time :2017年11月08日 星期三 18 …

题意： 求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后基数排序然后倒着更新就行了 ...代码之后补 关键是理解这句 …

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] = …

http://www.spoj.com/problems/SUBLEX/en/ 题意： 给一个字符串，每次询问字典序第k大的不重复子串。 思路： 先做个拓扑dp，求出SAM上，一个状态到种态的路径数。 拓扑dp其实就是按照拓扑序的dp啦... 然后从SAM的初始态开始，每次字典序从小到大得贪心寻找。思想类似可持久化线段树求区间第k大。 /* *********************************************** Author :111qqz Created Time :2017年11月08日 星期三 18时50分18秒 File Name :sublex.cpp …

http://www.spoj.com/problems/NSUBSTR/en/ 题意： f[i]指长度为i的串出现次数的最大值。这里的不同出现指，可以有重复串，只要起始位置不同就视为不同的出现。 求f[1]..f[lenth]。 思路： 我们知道，SAM上的节点是right集合的等价类。 一个子串的right集合是指在一个母串中，某个子串所有出现位置的右端点的集合。 如果两个子串的right集合完全相同，那么就可以归结为同一个节点，也就是说这两个子串对于SAM是等价的。 因为在SAM上，这两个子串后，添加若干字符得到的后缀都是一样的。 所以一个SAM节点的个数，就是right集合等价类的个数（如果不考虑初始状态） 对于SAM某一个 …

***在学习后缀自动机之前需要熟练掌握WA自动机、RE自动机与TLE自动机*** 怕是老年人的最后一篇算法学习笔记了 心情不好，此文无限期tj 概述 主要讲解在我学习的过程中比较难理解的地方..并不保证全面 首先，后缀自动机是一个能且只能接受一个字符串的所有后缀的确定性有限状态自动机，也就是DFA SAM同时具有自动机和树的性质。 节点（状态） SAM中的节点，也叫状态。 明确一个说法：“一个节点所表示的字符串”。 由于一个字符串的子串一定是某个后缀的前缀。 因此一个字符串的子串一定可以在SAM上运行。 因此“一个节点Q所表示的字符串”的含义是说，从初始状态开始，运行该字符串后，到达的状态是Q. 一个节点所表示的字符串长度属于范 …