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

hdu5787 题意:给出l,r,k求区间[l,r]中满足任意相邻k个数字都不相同的数的个数. 思路:数位dp,dp[i][k1][k2][k3][k4]表示长度为i,前1位是k1,前2位是k2,前3位是k3,前4位是k4的方案数. 注意不允许前导0.2A /* *********************************************** Author :111qqz Created Time :2016年08月02日 星期二 16时28分29秒 File Name :code/multi2016/#5/1007.cpp …

题目链接 题意：给出一个字符串，问所有不同的字串的个数。 思路：直接求比较困难。我们考虑，假如组成字符串的所有字符都不相同，那么就没有相同的字串，假设字符串的长度为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,但是 …

hdu1280 题意：给出n(3000)个数，两两求和，输出最大的m(5000)个和。 思路：由于数据有限，想到计数排序。。。以及，m个可能刚好某个数据没有全部输出，要在while里判断一下。。 。。。好好的人。。怎么开始刷水了。。。。。 其实是因为最近在看.suffix array...然后里面涉及到了radix sort..算法课的时候到是写过。。。不过快忘了orz。。所以打算找几道题目。。。？ 然而这是计数排序不是基数排序啊摔/！ /* *********************************************** Author :111qqz Created Time :2016年07月30日 星期六 17 …

原文链接：链接 讲了后缀数组的概念，然后从最暴力的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 …

1874: [BeiJing2009 WinterCamp]取石子游戏 Time Limit: 5 Sec Memory Limit: 162 MB Submit: 726 Solved: 296 [Submit][Status][Discuss] Description 小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的，每个人每次可以从一堆石子中取出若干个石子，每次取石子的个数有限制，谁不能取石子时就会输掉游戏。 小H先进行操作，他想问你他是否有必胜策略，如果有，第一步如何取石子。 Input 输入文件的第一行为石子的堆数N 接下来N行，每行一个数Ai，表示每堆石子的个数 接下来一行为每次取石子个数的种类数M 接下来M …