2.5 练习题
习题2-1
题目来源：HDU 5536。
题目类型：01字典树。
题目思路：把每个数字看成一个01字符串插入Trie树中去，枚举i和j，然后把si和sj从Trie树中删去。然后在Trie树中通过贪心算法找与si+sj异或得到的最大值。具体匹配的过程为：首先看树中最高位能否异或得到1，能的话就往能的那个方向走，否则往另外一个方向走。另外删除操作是这样实现的，每个节点记录一个val值，插入时对所有经过节点的val值加1，删除就将对应节点的val值减1。在树上匹配的时候就只走那些val值为正的节点。
习题2-2
题目来源：HDU 482。
题目类型：01字典树。
题目思路：求某个数与一些数异或的最大值，是字典树应用的一个经典问题。主要思想是贪心算法，将给定的数按照二进制构成一棵字典树，每一层分别对应各个位数上的01状态。然后进行查询，如果对应位置为0，则要往1的方向走；如果对应位置为1，则要往0的方向走。但是要注意，走的前提是对应分支是存在的。
习题2-3
题目来源：POJ 3764。
题目类型：01字典树。
题目思路：这道题是要在树中找两个节点，且两个节点之间路径唯一，求最长的异或路径。很明显不能用暴力算法，O（N2）时间复杂度为100000个点。首先需要知道一个性质：a⊕b=（a⊕c）⊕（b⊕c），这样就可以考虑找出a与b公共的c，实际上就是求出从根节点到每个节点的异或值，这样任意两个点做异或，即是它们之间的异或路径（相同部分异或抵消了）。先使用DFS（Depth First Search）方法遍历一遍，找出所有节点到树根的路径异或值，这样就将问题转化成了求这些点中任意两个点的异或值，接下来就很简单了，将使用DFS方法所得的每个点的异或值转化成二进制数后保存在字典树中，然后从高位至低位对字典树进行贪心搜索，找出最大的那个值即可。
习题2-4
题目来源：HDU 3746。
题目类型：KMP。
题目思路：题目要求的是给定一个字符串，还需要添加几个字符可以构成一个由n个循环节组成的字符串。由题目可知，应该先求出字符串的最小循环节的长度。假设字符串的长度为len，那么最小的循环节cir=len-next[len]；如果有len%cir==0，那么这个字符串就已经是要求的字符串了，不用添加任何字符；如果不是要求的那么需要添加的字符数为cir-（len-（len/cir）×cir））。如果cir=1，说明字符串只有一种字符，例如“aaa”；如果cir=m，说明最小的循环节长度为m，那么至少还需m个字符；如果m%cir==0，说明已经不用添加了字符。
习题2-5
题目来源：POJ 2406。
题目类型：KMP。
题目思路：对于next数组表示的模式串，如果第i位（设str[0]为第0位）与第j位不匹配，则要回到第next[i]位继续与模式串第j位匹配，则模式串第1位到next[n]与模式串第n-next[n]位到n位是匹配的。所以思路和上面一样，如果n%（n-next[n]）=0，则存在重复连续子串，长度为n-next[n]。
例如，“a b a b a b”，next[]={-1,0,0,1,2,3,4}，next[n]=4，代表前缀“abab”与后缀“abab”相等的最长长度，这说明，“ab”这两个字母为一个循环节，长度=n-next[n]。
习题2-6
题目来源：BZOJ 1717。
题目类型：后缀数组+二分法。
题目思路：先二分答案，然后将后缀分成若干组。判断有没有一个组的后缀个数不小于k。如果有，那么存在k个相同的子串满足条件，否则不存在。
习题2-7
题目来源：BZOJ 2251。
题目类型：后缀数组。
题目思路：首先根据后缀数组的一些经典应用，可以知道每个后缀对子串个数的贡献是n-H[i]-sa[i]，而且顺序就是字典序，枚举每个子串暴力的用H数组前后求匹配：L为向前最多到哪，R为向后最多到哪，答案是R-L。还有更简单的Trie树方法。
习题2-8
题目来源：BZOJ3238。
题目类型：后缀数组。
题目思路：首先这个式子可以拆成两部分计算，一部分是两个后缀长度之和，一部分是最长公共前缀（Longest Common Prefix，LCP）长度之和。第一部分很简单，发现每个长度的后缀都计算了n-1次，所以第一部分的答案为（n-1）×[n×（n+1）/2]，注意计算过程中需要强制类型转换。而第二部分和之前的一个模型类似，需要用到单调栈。两个后缀的LCP在h数组里其实就是一段区间的最小值，而反过来h数组每段区间的最小值对应着两个后缀的LCP，然后计算总和。单调栈维护一个递增的、用f[i]表示h数组中从i到n所有区间的LCP之和，每次计算f[i]，f[i]=f[st[top]]+h[i]×（st[top]-i），然后计入总和就行。
习题2-9
题目来源：HDU6194。
题目类型：后缀数组。
题目思路：先考虑至少出现k次的子串，所以枚举排好序的后缀i（sa[i]）。假设当前枚举的是sa[i]～sa[i+k-1]，假设这一段的最长公共前缀是L的话，那么就有L个不同的子串至少出现了k次，要减去至少出现k+1次的子串，但还要和这个k段的LCP有关系，因此肯定就是sa[i]～sa[i+k-1]这一段向上找一个后缀或者向下找一个后缀。即sa[i-1]～sa[i+k-1]和sa[i]～sa[i+k]求两次LCP减去即可。但是会减多了，减多的显然是sa[i-1]～sa[i+k]的LCP，加上即可。注意k=1的情况在求LCP会有问题，即求一个字符串的最长公共前缀会有问题，特判一下即可。