http://uoj.ac/problem/103 题意： 给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s 中出现的次数乘以这个子串的长度。 对于给你的这个字符串 s，求所有回文子串中的最大存在值。 思路： 回文自动机，也叫回文树，但其实并不是树2333,所以以后还是称为回文自动机，缩写为PAM 学会了(?)SAM之后再看PAM真是简单得一逼。 学习笔记之后补。 对于这道题，PAM中一个状态的cnt表示的该状态所表示的回文串出现的次数 len表示的是该状态所表示的回文串的长度 UPDATE: 下面的代码风格太丑了，打算弃用。 更新的代码风格见最后 #include …

题目链接：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=6059 题意： 含 N 个数字的 A 数组，求有多少个三元组 (i,j,k) 满足 i<j<k 且a[i]^a[j] < a[j]^a[k] 思路: 考虑a[i]和a[k]二进制不同位中的最高位，此时满足题意的a[j]是该位与a[i]相同，其他位任意的所有a[j]的个数。 我们可以从1..n，依次插入a[k]到trie中,插入时，顺便用num[i][j]统计二进制第i位为j的数的个数。 当要插入a[k]时，a[1]..a[k-1]已经插入到了trie中。 trie上统计当某个节点，该位为0的数的个数和该为为1的数的个数。 需要注意 …

题目链接： 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=4819 题意： 给你一个n*n的矩阵， 每个点是一个数字， Q个操作，每次选择一个子矩阵， 把中心元素替换成子矩阵中最大值和最小值之和的二分之一。 思路: 显然是一个二维线段树..... 然而菜鸡如我，并没有写过二维线段树啊？ 那怎么办呢 一首《凉凉》送给自己 然而我们还有四叉树2333 2A，写错一个地方。第一次写四叉树，orz #include <bits/stdc++.h> #define ms(a,x) memset(a,x,sizeof(a)) #define lowbit(x) (x&(-x)) using …

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