总结了几天的后缀数组，终于完成了。

不可重叠重复串;

可重叠k次重复串;

不相同子串个数

最长回文子串

连续重复子串

重复次数最多的连续重复子串

最长公共子串

长度不小于k 的公共子串的个数

不小于k 个字符串中的最长子串

出现或反转后出现在每个字符串中的最长子串

3个字符串，问其中公共子串分别为1,2,3...l的有多少个

快速通道：http://poj.org/problem?id=1743

题意：有N(1<= N<=20000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，现在要找一个重复的主题。“主题”是整个音符序列的一个子串，它需要满足如下条件：

1.长度至少为5个音符。

2.在乐曲中重复出现。(可能经过转调，“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值)

3.重复出现的同一主题不能有公共部分。

思路：利用后缀数组的高度数组，然后二分一个长度判断是否可行，判断可行性只要二分1个长度len,然后在满足height[i]>=len的所有情况下的一个最大差值是否大于len就可以了。

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/poj1743.cpp

新技能：后缀数组，不可重叠重复串

快速通道：http://poj.org/problem?id=3261

题意：一个字符串，里面是否存在k次重复子串，子串可重叠

思路：还是分组，这里的分组一定要在第一个大于二分的长度里面去找，因为这样才代表相邻2串的height值，而不是整个height数组，这点一定要分清楚，因为整个height数组求的是所有后缀，有时景观他的height值大于二分值，但他所表示的并不是相同的子串，毕竟题目要求要重复，然后其他就和上面一题一样了。

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/poj3261.cpp

新技能：后缀数组，可重叠k次重复串

快速通道：http://www.spoj.com/problems/DISUBSTR/

题意：求一个字符串不相同的子串的个数。

思路：每个子串一定是某个后缀的前缀,那么原问题等价于求所有后缀之间的不相同 的 前 缀 的 个 数 。 如 果 所 有 的 后 缀 按 照suffix(sa[1]), suffix(sa[2]), suffix(sa[3]),...... ,suffix(sa[n])的顺序计算,不难发现,于每一次新加进来的 后缀 suffix(sa[k]), 它将产生n-sa[k]+1 个新的前缀。但 是其中有 height[k]个是和前面的字符串的前缀是相同的。所以suffix(sa[k])将“贡献”出 n-sa[k]+1- height[k]个不同的子串。累加后便是原问题的答案。

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/spoj694.cpp

新技能：后缀数组，不相同子串个数

快速通道：http://www.spoj.com/problems/SUBST1/

题意：和上一题一样，只是数据量变大了。

思路：和上一题一样，只是数据量变大了。

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/spoj694.cpp（MAX_N=50007,len变成longlong）

新技能：后缀数组，不相同子串个数

快速通道：http://acm.timus.ru/problem.aspx?space=1&num=1297

题意：求字符串的最长回文子串。

思路：穷举每一位,然后计算以这个字符为中心的最长回文子串。注意这里要分两种情况,一是回文子串的长度为奇数,二是长度为偶数。两种情况都可以转化为求一个后缀和一个反过来写的后缀的最长公共前缀。具体的做法是:将整个字符串反过来写在原字符串后面,中间用一个特殊的字符隔开。这样就把问题变为了求这个新的字符串的某两个后缀的最长公共前缀。

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/ural1297.cpp

新技能：后缀数组，最长回文子串

快速通道：http://poj.org/problem?id=2406

题意：给定一个字符串L,已知这个字符串是由某个字符串S 重复R 次而得到的,求R 的最大值。

思路：做法比较简单,穷举字符串S 的长度k,然后判断是否满足。判断的时候,先看字符串L 的长度能否被k 整除,再看suffix(1)和suffix(k+1)的最长公共前缀是否等于 n-k。在询问最长公共前缀的时候,suffix(1)是固定的,所以RMQ 问题 没 有 必 要 做 所 有 的 预 处 理 ,只需 求 出 height 数组 中 的 每 一 个 数 到

height[rank[1]]之间的最小值即可。整个做法的时间复杂度为O(n) ,还有一种KMP亦可解。

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/poj2406.cpp

新技能：后缀数组，连续重复子串

快速通道：http://www.spoj.com/problems/REPEATS/

题意：给定一个字符串,求重复次数最多的连续重复子串

思路：先穷举长度L,然后求长度为L 的子串最多能连续出现几次。首先连续出现1 次是肯定可以的,所以这里只考虑至少2 次的情况。假设在原字符串中连续出现 2 次,记这个子字符串为S,那么S 肯定包括了字符r[0],r[L], r[L*2], r[L*3], ......中的某相邻的两个。所以只须看字符r[L*i]和r[L*(i+1)]往前和往后各能匹到多远,记这个总长度为K,那么这里连续出现了K/L+1 次。最后看最大值是多少。如图 7 所示。穷举长度 L 的时间是n,每次计算的时间是n/L。所以整个做法的时间复杂度是 O(n/1+n/2+n/3+......+n/n)=O(nlogn)

这里的向后匹配就是lcp(j,j+l),向前匹配就是算pre=l-k%l，表示前面还剩下多少个未匹配，然后计算lcp(j-pre,j-pre+l)的长度是否大于pre就可以了，然后结果再+1，表示还有一个循环节要加到结果中。

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/spoj687.cpp

新技能：后缀数组，重复次数最多的连续重复子串

快速通道：http://poj.org/problem?id=3693

题意：给定一个字符串,求重复次数最多的连续重复子串

思路：和上一题基本一样。只是这一题要求如果多种情况要字典序最小输出，这个可以先把重复次数的最多的情况存到数组里面记录下来，然后在再结果里面去扫sa,因为sa就是字典序的最小状态，然后判断这样能否组成的字段个数等于xans，那么便是答案。

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/spoj3693.cpp

新技能：后缀数组，重复次数最多的连续重复子串

快速通道：http://poj.org/problem?id=2774

题意：给定两个字符串A 和B,求最长公共子串

思路：把B接在A后面，求height数组中最大的即可，判断2个子串是否在不同原串中，只要sa[i-1]和sa[i]在不同即可。

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/poj2774.cpp

新技能：后缀数组，最长公共子串

快速通道：http://acm.timus.ru/problem.aspx?space=1&num=1517

题意：给定两个字符串 A 和B,求最长公共子串

思路：同上，只是这一题要记录位置，然后输出。

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/poj2774.cpp

新技能：后缀数组，最长公共子串

快速通道：http://poj.org/problem?id=3415(重难点：单调栈)

题意：长度不小于k 的公共子串的个数

思路：把两个串拼接起来，中间用神奇地‘$‘字符隔开。然后用倍增算法求sa数组、rank数组、height数组，然后利用height数组统计第一个串称A串的所有后缀与第二个串B串的所有后缀所共有的长度大于k的子串。

上面的逻辑过程容易理解，用aa和aa就能推出为什么答案是5，子串a有2个，aa有1个，2*2+ 1*1 =5.问题的关键是要找出各个子串总匹配数（子串相等称为匹配）。height数组表示的是和其他串所有最长公共前缀中的最长公共前缀，也是和前一个串的公共前缀，用这个数组就可以求出总匹配数。height[i]-k+1代表和前一个子串相比符合条件的匹配数，如果height[i]大于它属于组内（根据height[i]是否大于k分组，height数组是波浪形，很容易分组）前面的每一个height[j]的话，就可以一次一次和前面的height[j]比较如果是大于，就增加height[i]-k+1,这就代表从sa[i]开始的后缀与sa[j]开始的后缀有height[i]-k+1个相等的串，一旦小于，就应该做些处理，把多出来的那部分去掉，因为这部分以后再也不会有相等的串了，没什么价值了。但这样，复杂度是O(n^2),可用单调栈优化，具体实现见代码.

这里说一下单调递增栈的原理：对与一系列height值，假设有1，2，3，4，5，3，2,依次加入1,2,3,4,5的时候，依次入栈就好了，不用判断，那么当加入3的时候，这时候就要弹出5,4，3了，这个弹出了的时候给这个3的权加上3，代表前面有3个数比他大，然后就好计算啦。

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/poj3415.cpp

新技能：后缀数组，长度不小于k 的公共子串的个数

快速通道：http://poj.org/problem?id=3294（dc3）

题意：给定n 个字符串,求出现在不小于k （大于n/2）个字符串中的最长子串

思路：二分最长长度后，判断是否存在大于n/2的，然后输出可能多种答案，所以只要找到满足的就输出。然后这里分段链接的时候一定要用不同的字符链接，负责他的height值也会变。

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/poj3294.cpp

新技能：后缀数组，不小于k 个字符串中的最长子串

快速通道：http://www.spoj.com/problems/PHRASES/

题意：n个字符串,求在每个字符串中至少出现两次且不重叠的最长子串

思路：做法和上题大同小异,也是先将n个字符串连起来,中间用不相同的且没有出现在字符串中的字符隔开,求后缀数组。然后二分答案,再将后缀分组。判断的时候,要看是否有一组后缀在每个原来的字符串中至少出现两次,并且在每个原来的字符串中,后缀的起始位置的最大值与最小值之差是否不小于当前答案。

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/spoj220.cpp

新技能：后缀数组，每个字符串至少出现两次且不重叠的最长子串

快速通道：http://poj.org/problem?id=1226

题意：出现或反转后出现在每个字符串中的最长子串

思路：这题不同的地方在于要判断是否在反转后的字符串中出现。

其实这并没有加

大题目的难度。只需要先将每个字符串都反过来写一遍,中间用一个互不相同的且没有出现在字符串中的字符隔开,再将n个字符串全部连起来,中间也是用一个互不相同的且没有出现在字符串中的字符隔开,求后缀数组。然后二分答案,再将后缀分组。判断的时候,要看是否有一组后缀在每个原来的字符串或反转后的字符串中出现.

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/poj1226.cpp

新技能：后缀数组，出现或反转后出现在每个字符串中的最长子串

快速通道：http://codeforces.com/problemset/problem/452/E

题意：给出3个字符串，问其中公共子串分别为1,2,3...l的有多少个，l<min(|s1|,|s2|, |s3|).

思路：对高度数组的排名进行操作。我们首先得到c[i][j]表示排名为1～i的1，2，3串分别有多少个，j就记录1,2,3的状态，还有就是v[i]记录lcp值为i的有哪些。然后假如3个串都同一个字符，那么答案就是d=l1*l2*l3,所以当我们求长度为1的有多少个的时候，肯定就是分别在1,2,3串中同时出现且不重复的字符，

那么计算1的时候就是把减去lcp为0的就可以了，计算2的时候就是减去lcp为1的。。。所以现在的重点就是怎么计算这个数量。我们首先用set维护一对(1,n)，计算1的时候，我们依次弹出v[0]里面的全部位置，然后二分这个位置，计算是否符合，然后加入到结果中。（hint:因为这题要三串共有，所有要用类似前缀和的思想）

代码：https://github.com/Mithril0rd/ComplexCode/blob/master/cf452e.cpp

新技能：3个字符串，问其中公共子串分别为1,2,3...l的有多少个

【后缀数组】总结