Description 顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。 输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。 Input 一行由小写英文字母组成的字符串S。 Output 一行一个整数，表示最长双回文子串的长度。 Sample Input baacaabbacabb Sample Output 12 HINT 样例说明 从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。 对于100%的数据，2≤|S|≤10^5 …

http://acm.hdu.edu.cn/showproblem.php?pid=3948 题意： 给一个字符串，问本质不同的回文子串的个数。 思路： 考虑回文自动机。 我们知道，对于PAM上的一个节点，表示的就是一个本质不同的回文串。 UPDATE: 弃用了这种代码风格,新的写法见下面。 那么sz-2就是本质不同的回文子串个数了orz(减掉2是因为PAM有2个根，这2个根不表示回文串） #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> typedef long long LL; …

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