poj3261 题意：给一个字符串，要求找出至少出现k次的最长重复子串... 思路：后缀数组，然后再次用到了根据height数组对后缀进行分组的套路...二分判定合法性，对于当前的最长长度x,分组使得每组中的height[i]都大于等于x,所不同的是，判定变成了存在一个组，后缀的个数至少为k个（因为这样，就可以对于大于等于k个的后缀，同时取前x长度，得到的就是出现了至少k次且长度为x的前缀）1A,蛤蛤蛤 /* *********************************************** Author :111qqz Created Time :2016年08月01日 星期一 01时30分34秒 File Name …

poj 1743 题意：n个数字（1..88）表示的音符，问最长的连续两段长度至少为5的变化相同的音符段的长度。。。 思路：求最长重复字串。。。。很容易想到后缀数组。。但是这道题多了一个不可重叠的要求。 先二分答案,把题目变成判定性问题:判断是否 存在两个长度为 k 的子串是相同的,且不重叠。解决这个问题的关键还是利用 height 数组。把排序后的后缀分成若干组,其中每组的后缀之间的 height 值都 不小于 k。例如,字符串为“aabaaaab”,当 k=2 时,后缀分成了 4 组,如图 5 所示。 容易看出,有希望成为最长公共前缀不小于 k 的两个后缀一定在同一组。然 后对于每组后缀,只须判断每个后缀的 sa 值的最大值和 …

ural1517 题意：给出两个字符串，求最长的公共字串（要求出具体的字符串是什么） 思路：依然是后缀数组，在更新长度 的时候记录起始位置即可，1A。以及，发现多开了一个完全没有必要的数组w[],这次已删。 20160730update:模板已更正，lrj的模板的rk[i]为0 的时候会出现re的问题...已特判。 /* *********************************************** Author :111qqz Created Time :2016年07月31日 星期日 00时36分19秒 File Name :code/ural/1517.cpp …

poj2774 题意：给出两个字符串，问最长的公共连续字串。 思路：后缀数组模板题。 具体可以参考两篇国集论文（09，04） topcoder中的讲解 codechef上的讲解 还有一篇讲 dc3算法的论文：SuffixArrays_dc3 这里不谈具体的后缀数组的学习内容，说说大概的学习过程。 首先要理解**后缀，后缀数组（sa[]），名次数组(rk[])，height数组，lcp **这些概念 先从定义入手，得到sa数组的n2logn的求法... 由于复杂度爆炸，所以有了两个算法来优化求sa的过程，一个是nlogn的倍增，还有一个是O(n)的dc3。。。 倍增的算法中用到了radix sort 上面这些，都是在说如何求sa,但是 …