字符串匹配（后缀数组）
假设已经求出字符串S的后缀数组点击打开链接，现在要求字符串T在字符串S中出现的位置，只要通过二分搜索就可以在O（T*logS）时间内完成。当S比较大时，比O（T+S）的算法更为高效，所以需要对同样的字符串做多次匹配时，该算法更有优势。代码：boolcontain(stringS,int*sa,str...
[BZOJ]4199: [Noi2015]品酒大会（后缀数组+笛卡尔树）
TimeLimit:10Sec MemoryLimit:512MBDescriptionInputOutputSampleInput10ponoiiipoi2147483647SampleOutput4556105633200000000000000HINTSolution先求出后缀数组，两个后缀...
POJ 1743 Musical Theme（后缀数组+二分答案）
【题目链接】 http://poj.org/problem?id=1743【题目大意】给出一首曲子的曲谱，上面的音符用不大于88的数字表示，现在请你确定它主旋律的长度，主旋律指的是出现超过一次，并且长度不小于5的最长的曲段，主旋律出现的时候并不是完全一样的，可能经过了升调或者降调，也就是说，是原来主...
poj 3693 Maximum repetition substring (后缀数组)
其实是论文题。。题意：求一个字符串中，能由单位串repeat得到的子串中，单位串重复次数最多的子串。若有多个重复次数相同的，输出字典序最小的那个。解题思路：其实跟论文差不多，我看了很久没看懂，后来总算理解了一些。假设我们的单位串长度为l，那么我们将串划分为s[0],s[l],s[2*l],s[3*l...
数据结构之后缀数组suffix array
在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树大家了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在信息学竞赛中后缀数组比后缀...
【模板】BZOJ 1692:队列变换—后缀数组 Suffix Array
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1692题意：给出一个长度为N的字符串，每次可以从串头或串尾取一个字符，添加到新串中，使新串的字典序最小。做法：经过推导（略），发现只要贪心地取两端字典序较小的一端，所以在一开始对所有的正反后缀排...
POJ 1743 (后缀数组+不重叠最长重复子串)
题目链接: http://poj.org/problem?id=1743题目大意：楼教主の男人八题orz。一篇钢琴谱，每个旋律的值都在1~88以内。琴谱的某段会变调，也就是说某段的数可以加减一个旋律范围的值。问这个谱子内最长不重叠的重复部分大小。解题思路：网上题解已经泛滥的题。很多细节都被先辈大神总...
hdu_5769_Substring(后缀数组)
题目链接：hdu_5769_Substring题意：给你一个字符a和一个串b，问你有多少个包括a的字串题解：#include<bits/stdc++.h>#defineF(i,a,b)for(inti=a;i<=b;++i)usingnamespacestd;typedeflong...
利用后缀数组(suffix array)求最长公共子串(longest common substring)
摘要：本文讨论了最长公共子串的的相关算法的时间复杂度，然后在后缀数组的基础上提出了一个时间复杂度为o(n^2*logn)，空间复杂度为o(n)的算法。该算法虽然不及动态规划和后缀树算法的复杂度低，但其重要的优势在于可以编码简单，代码易于理解，适合快速实现。首先，来说明一下，LCS通常指的是公共最长子...
URAL 1297 Palindrome（后缀数组+ST表）
【题目链接】 http://acm.timus.ru/problem.aspx?num=1297【题目大意】求最长回文子串，并输出这个串。【题解】我们将原串倒置得到一个新的串，加一个拼接符将新串拼在原串的后面，那么枚举对称的中心点，在两个串在组合成的串的对应位置的后缀的最长公共前缀就是该点像两边扩展...
suffix array后缀数组
倍增算法基本定义子串：字符串S的子串r[i..j]，i≤j，表示r串中从i到j这一段也就是顺次排列r[i],r[i+1],...,r[j]形成的字符串。后缀：后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字串r的从第i个字符开始的后缀表示为Suffix(i)，也就是Suffix(i)=r[...
AHOI2013 差异 【后缀数组】
题目分析：求出height以后很明显跨越最小height的一定贡献是最小height，所以对于区间找出最小height再将区间对半分。代码：#include<bits/stdc++.h>usingnamespacestd;constintmaxn=;constintN=;intn;cha...
POJ 3261 Milk Patterns（后缀数组+二分答案+离散化）
题意：给定一个字符串，求至少出现k次的最长重复子串，这k个子串可以重叠。分析：经典的后缀数组求解题：先二分答案，然后将后缀分成若干组。这里要判断的是有没有一个组的符合要求的后缀个数（height[i]>=mid）不小于k。如果有，那么存在k个相同的子串满足条件，否则不存在。#include&l...
【BZOJ2946】公共串（后缀数组）
【BZOJ2946】公共串（后缀数组）题面权限题。。。只有CJOJ题面啦Description给出几个由小写字母构成的单词，求它们最长的公共子串的长度。任务：读入单词，计算最长公共子串的长度Input第一行是整数n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成...
洛谷.3809.[模板]后缀排序(后缀数组 倍增) & 学习笔记
题目链接//输出ht见UOJ.35#include<cstdio>#include<cstring>#include<algorithm>constintN=1e6+5;intn,tm[N],t1[N],t2[N],SA[N],rk[N],ht[N];//SA[i...
POJ-3450 Corporate Identity (KMP+后缀数组)
DescriptionBesideotherservices,ACMhelpscompaniestoclearlystatetheir“corporateidentity”,whichincludescompanylogobutalsoothersigns,liketrademarks.Oneofs...
[Luogu5161]WD与数列(后缀数组/后缀自动机+线段树合并)
https://blog.csdn.net/WAautomaton/article/details/85057257解法一：后缀数组显然将原数组差分后答案就是所有不相交不相邻重复子串个数+n*(n-1)/2。答案=重复子串个数-相邻或相交重复子串个数。前者单调栈直接求解，注意细节，重点在后者。由于是...
后缀数组(suffix array)
参考：Suffixarray-Wiki后缀数组(suffixarray)详解6.3 SuffixArrays-算法红宝书SuffixArray后缀数组基本概念应用：字符串处理、生物信息序列处理后缀：学过英语的都知道什么叫后缀，就是从某个位置开始到字符串结尾的特殊子串，记住Suffix(i)=S[i...
hdu-6194 string string string 后缀数组 出现恰好K次的串的数量
最少出现K次我们可以用Height数组的lcp来得出，而恰好出现K次，我们只要除去最少出现K+1次的lcp即可。#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>...
bzoj 2251: [2010Beijing Wc]外星联络 后缀数组
2251:[2010BeijingWc]外星联络TimeLimit:30Sec MemoryLimit:256MBSubmit:424 Solved:232[Submit][Status][Discuss]Description小P在看过电影《超时空接触》(Contact)之后被深深的打动，决心...