题目链接 题意：把一个长度为n的只由数字构成的串分成k个不为空的字串，使得最大的串最小（大小是说串所对应的十进制数的大小） 思路：由于长度为x的串肯定大于长度为x-1的串，因此很容易想到，我们要尽可能使得k组串的长度尽可能平均（避免出现某一个串的长度非常大的情况） 我们可以知道，最大值的串的长度一定为 LEN=(n+k-1)/k; 而每一组的长度，只可能是LEN或者LEN-1。 然后build_sa 注意循环串的几个地方记得%n 接下来二分sa数组的下标。 二分check的时候，先枚举断点，断环为链。 由于每部分最长的长度为LEN，所以0..LEN-1中一定存在一个断点。 然后贪心，尽可能取LEN 根据rk值来决定某一段的长度 …

题目链接 题意：定义一个函数F．． For exampe: _F_(_babbabbababbab_, _babb_) = 6. The list of pairs is as follows: (1, 4), (4, 7), (9, 12) Its continuous sequences are: * (1, 4) * (4, 7) * (9, 12) * (1, 4), (4, 7) * (4, 7), (9, 12) * (1, 4), (4, 7), (9, 12) erfen ． erfen 题目描述得很烂．．看例子把．．大概就是：如果字符串y在字符串x中出现n次，那 …

poj 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) …

题目连接 题意：求所有不同的子串个数。 思路：后缀数组。和上一道题一样，就是数据范围变成了 5E4...1A /* *********************************************** Author :111qqz Created Time :2016年08月02日 星期二 18时32分28秒 File Name :code/spoj/subst1.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> …

题目链接 题意：给出一个字符串，问所有不同的字串的个数。 思路：直接求比较困难。我们考虑，假如组成字符串的所有字符都不相同，那么就没有相同的字串，假设字符串的长度为n，那么长度为1的子串有n个，为2的有n-1个。。。为n的有1个，一共就是n*(n+1)/2个。。但是实际上会有重复的。。。 我们再次考虑这张图。 先找一个字符重复的个数，对应height[i]数组就是找height[i]大于等于1个的个数（因为x个height代表了x+1个后缀，保留1个，重复了x个，所以重复的个数恰好和符合条件的height数组对应） 接着找大于等于2的个数，大于等于3的个数... 最后再把所有答案累加起来，就是总共重复的次数。 然后按照我推出的这个结 …

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,但是 …

原文链接：链接 讲了后缀数组的概念，然后从最暴力的O(nnlogn )的复杂度(O(n)用来比较字符串，O(nlogn)是排序的复杂度)逐步优化，依据各个串之间的关系，大概讲了倍增算法，以及给出了一篇The Skew Algorithm 的论文。 文中实现的倍增算法的复杂度是O（Nlog2N）的。。是因为作者不会基数排序23333。 This text will focus on the construction of Suffix Arrays, it will aim to explain what they are and what they are used for and hopefully some examples …