SPOJ705-New Distinct Substrings-后缀数组
计算所都不相同子串的个数，做法是所有子串的个数减去sigma(height[]).其中height数组的和便是所有相同子串的个数。注意 N×(N+1)/2会爆int！但是最终答案在int内。所以使用sigma（n-sa[i]+1-height[i]）的做法不会wa #include <cstd...
spoj 694. Distinct Substrings 后缀数组求不同子串的个数
题目链接：http://www.spoj.com/problems/DISUBSTR/思路：每个子串一定是某个后缀的前缀,那么原问题等价于求所有后缀之间的不相同的前缀的个数。如果所有的后缀按照suffix(sa[1]),suffix(sa[2]),suffix(sa[3]),……suffix(sa[...
POJ 2406 KMP/后缀数组
题目链接：http://poj.org/problem?id=2406题意:给定一个字符串，求由一个子串循环n次后可得到原串，输出n[即输出字符串的最大循环次数]思路一：KMP求最小循环机，然后就能求出循环次数。#define _CRT_SECURE_NO_DEPRECATE#include<...
POJ 3261 Milk Patterns 后缀数组求 一个串种 最长可重复子串重复至少k次
Milk Patterns DescriptionFarmer John has noticed that the quality of milk given by his cows varies from day to day. On further investigation, he disco...
Poj 1743 Musical Theme(后缀数组+二分答案)
Musical Theme Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 28435 Accepted: 9604 Description A musical melody is repr...
Poj 3261 Milk Patterns(后缀数组+二分答案)
Milk Patterns Case Time Limit: 2000MS Description Farmer John has noticed that the quality of milk given by his cows varies from day to day. On fu...
poj 3294 Life Forms - 后缀数组 - 二分答案
题目传送门传送门I传送门II题目大意给定$n$个串，询问所有出现在严格大于$\frac{n}{2}$个串的最长串。不存在输出'?'用奇怪的字符把它们连接起来。然后求sa，hei，二分答案，按mid分组。判断每一组存在的后缀属于的原串的种类数是不是存在那么多个。这个做法可以推广到多串求LCS，然后多个...
POJ 3261 Milk Patterns(后缀数组+单调队列)
题意找出出现k次的可重叠的最长子串的长度题解用后缀数组。然后求出heigth数组。跑单调队列就行了。找出每k个数中最小的数的最大值。就是个滑动窗口啊（不知道为什么有人写二分，其实写啥都差不多快，可能是因为二分是一个常见的模型吧） #include<iostream> #include&l...
POJ 1226 Substrings（后缀数组+二分答案）
【题目链接】 http://poj.org/problem?id=1226【题目大意】求在每个给出字符串中出现的最长子串的长度，字符串在出现的时候可以是倒置的。【题解】我们将每个字符串倒置，用拼接符和原串拼接，然后将所有通过这种方式得到的字符串拼接，做后缀数组，因为求最长子串，所以我们考虑二分答案后...
POJ 3261 Milk Patterns ( 后缀数组 && 出现k次最长可重叠子串长度 )
题意 : 给出一个长度为 N 的序列，再给出一个 K 要求求出出现了至少 K 次的最长可重叠子串的长度分析 : 后缀数组套路题，思路是二分长度再对于每一个长度进行判断，判断过程就是对于 Height 数组进行限定长度的分组策略，如果有哪一组的个数 ≥ k 则说明可行！分组要考虑到一个事实，对于每一...
K-th occurrence HDU - 6704 (后缀数组+二分线段树+主席树)
大意: 给定串s, q个询问(l,r,k), 求子串s[l,r]的第kk次出现位置.这是一篇很好的题解：https://blog.csdn.net/sdauguanweihong/article/details/100063096加点个人：我对上面的题解更为详细的解释下：后缀数组处理出来的heigt...
POJ 2774 Long Long Message （后缀数组模板）
借用罗大神的模板，开始搞后缀数组#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;#define N 222222...
[bzoj2251][2010Beijing Wc]外星联络——后缀数组+暴力求解
Brief Description找到 01 串中所有重复出现次数大于 1 的子串。并按字典序输出他们的出现次数。Algorithm Design求出后缀数组之后，枚举每一个后缀，对于每个后缀从height[i]+1枚举（因为height[i]之前已经计算过了），然后对于这样的每个前缀看一看上下能够...
BZOJ_2251_[2010Beijing Wc]外星联络_后缀数组
BZOJ_2251_[2010Beijing Wc]外星联络_后缀数组Description小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星人发来的信息。虽然他收听到的仅仅是一些噪声，但是他还是按照...
【BZOJ2251】[2010Beijing Wc]外星联络 后缀数组
【BZOJ2251】[2010Beijing Wc]外星联络Description小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星人发来的信息。虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的...
2251. [2010Beijing Wc]外星联络【后缀数组】
Description小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星人发来的信息。虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高低电平将接收到的信号改写为由 0 和 1 构成的串， 并坚...
字符串匹配（后缀数组）
假设已经求出字符串S的后缀数组点击打开链接，现在要求字符串T在字符串S中出现的位置，只要通过二分搜索就可以在O（T*logS）时间内完成。当S比较大时，比O（T+S）的算法更为高效，所以需要对同样的字符串做多次匹配时，该算法更有优势。 代码： bool contain(string S,...
BZOJ 2865 字符串识别 | 后缀数组 线段树
集训讲字符串的时候我唯一想出正解的题……链接BZOJ 2865题面给出一个长度为n (n <= 5e5) 的字符串，对于每一位，求包含该位的、最短的、在原串中只出现过一次的子串。题解“只出现过一次”，想到后缀数组，后缀数组可以求出以第i位开头的最短的在原串中只出现过一次的子串——它的长度是mi...
URAL 1297 Palindrome（后缀数组+ST表）
【题目链接】 http://acm.timus.ru/problem.aspx?num=1297【题目大意】求最长回文子串，并输出这个串。【题解】我们将原串倒置得到一个新的串，加一个拼接符将新串拼在原串的后面， 那么枚举对称的中心点， 在两个串在组合成的串的对应位置的后缀的最长公共前...
POJ-3261-Milk Patterns(后缀数组)
题意:给定一个字符串，求至少出现k 次的最长重复子串，这k 个子串可以重叠。分析:先二分答案，然后将后缀分成若干组。不同的是，这里要判断的是有没有一个组的后缀个数不小于k。如果有，那么存在k 个相同的子串满足条件，否则不存在。这个做法的时间复杂度为O(nlogn)。// File Name: 326...