UVALive4513 Stammering Aliens（哈希法，后缀数组）
题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=12580【思路】求出现次数不小于k次的最长可重叠子串和最后的出现位置。法一：后缀数组，二分长度，划分height。时间复杂度为O(nlogn)法二：Hash法。构造字符...
bzoj3238 [Ahoi2013]差异 后缀数组+单调栈
【bzoj3238】[Ahoi2013]差异DescriptionInput一行，一个字符串SOutput一行，一个整数，表示所求值Sample InputcacaoSample Output54题解：任意两个字符串的lcp是什么，就是如a,b 那么若a==b 那么为len(a)否则设sa[a]&...
BZOJ 3238: [Ahoi2013]差异 [后缀数组 单调栈]
3238: [Ahoi2013]差异Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 2326 Solved: 1054[Submit][Status][Discuss]DescriptionInput一行，一个字符串SOutput一行，一个整数，表示...
【POJ11855】 Buzzwords （后缀数组）
DescriptionThe word “the” is the most commonthree-letter word. It evenshows up inside other words, suchas “other” and “mathematics”.Sometimes it hides...
[LOJ#6198]谢特[后缀数组+trie+并查集]
题意给你一个长度为 \(n\) 的字符串，问 \(LCP(i,j)+(w_i\ xor\ w_j)\) 的最大值，其中 \(LCP\) 表示两个后缀的最长公共前缀。\(n\le 10^5\)分析建立 \(SA\) 之后把所有的 \(height\) 从大到小加入，维护连通块(类似 \(MST\) )...
后缀数组：HDU1043 Longest Common Substring
Longest Common SubstringTime Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5375 Accepted Submi...
3.27模拟赛 sutoringu(后缀数组)
\(\color{white}{mjt是机房模拟赛独自切过题的唯一的人...}\)（应本人要求删掉惹）\(Description\)给你\(n,k\)和长为\(n\)的字符串\(s\)。一个区间\([l,r]\)是合法的，当且仅当\(s[l...r]\)能被分成\(k\)个相同的子串。求有多少个合法...
[BZOJ]4199: [Noi2015]品酒大会（后缀数组+笛卡尔树）
Time Limit: 10 Sec Memory Limit: 512 MBDescriptionInputOutputSample Input10ponoiiipoi2 1 4 7 4 8 3 6 4 7Sample Output45 5610 563 320 00 00 00 00 00 0...
【SPOJ687&POJ3693】Maximum repetition substring（后缀数组）
题意： n<=1e5 思路： From http://hzwer.com/6152.html 往后匹配多远 r 用ST表求lcp即可。。。往前 l 就把串反过来再做一下。。 但是有可能求出来的最长串可以前移/后移几位即开头可以在落在[i−l,i−l+(l+r)mod L] 区间内字典序最小...
[POJ3415]Common Substrings（后缀数组+单调栈）
题目描述 传送门 题意：给定两个字符串 A 和 B ，求长度不小于 k 的公共子串的个数（可以相同）。 题解 首先把一个串接在另一个串的后面，中间放一个没出现过的字符。 由于每一个子串都是某一个后缀的前缀，求出sa和height了之后，我们可以将height分组，组内都是height&...
[JSOI2007]字符加密 后缀数组
题面：洛谷题解：我们考虑，如果可以将环上每个长度为len的串都提取出来，再做个排序，那这题我们就做出来了！但是提取$n^2$,怎么办？考虑破环成链，再扩充为原来的2倍。然后直接做后缀排序，把长度大于len的串按排序结果顺次列下来，对于每个后缀取出前len个字符构成串，最后得到的就是我们要的排序结果。...
hdu4691 Front compression ——暴力 || 后缀数组
link:http://acm.hdu.edu.cn/showproblem.php?pid=4691暴力，数据明显太水了吧，n=10^5, O(n^2)的复杂度哎喂。想让大家暴力写直接让n=1000不就得了么，这算什么。 #include <iostream> #include <...
Codeforces 432D Prefixes and Suffixes (KMP、后缀数组)
题目链接: https://codeforces.com/contest/432/problem/D题解:做法一: KMP显然next树上\(n\)的所有祖先都是答案，出现次数为next树子树大小。做法二: 后缀数组/Z-box按照height分组，二分查找即可。这种题经常KMP和Z-box都能做。...
HDU 3518 Boring counting（后缀数组，字符处理）
题目参考自：http://blog.sina.com.cn/s/blog_64675f540100k9el.html题目描述：找出一个字符串中至少重复出现两次的字串的个数（重复出现时不能重叠）。解题报告：后缀数组即可解之。枚举字串长度h对于每一次的h，利用height数组，找出连续的height大于...
ACdream 1430 SETI 后缀自动机/后缀数组 不重叠子串的个数
题目求不重叠子串的个数。 一开始看错题第一反应就是用SAM来解，求出right集，如果出现次数超过1次就统计。 不过本题要求的是不重叠的子串，因此在求right集时，顺便维护两个值，每个结点所能表示的所有原串的终点的最小值和最大值。 最后遍历所有结点统计答案。O(n) 如果用SA来做的话就是枚举所有...
Long Long Message （poj2774 后缀数组求最长公共子串）
Long Long Message Time Limit: 4000MS Memory Limit: 131072K Total Submissions: 19206 Accepted: 7934 Case Time Limit: 100...
「kuangbin带你飞」专题十八 后缀数组
layout: posttitle: 「kuangbin带你飞」专题十八 后缀数组author: "luowentaoaa"catalog: truetags:- kuangbin- 字符串- 后缀数组传送门倍增法struct DA{ bool cmp(int *r...
BZOJ 1692: [Usaco2007 Dec]队列变换 [后缀数组 贪心]
1692: [Usaco2007 Dec]队列变换Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1383 Solved: 582[Submit][Status][Discuss]DescriptionFJ打算带他的N(1 <= N <= 3...
poj 3261 Milk Patterns（后缀数组）(k次的最长重复子串)
Milk PatternsTime Limit: 5000MS Memory Limit: 65536KTotal Submissions: 7938 Accepted: 3598Case Time Limit: 2000MSDescriptionFarmer John has noticed th...
BZOJ 2946 [Poi2000]公共串 (二分+Hash/二分+后缀数组/后缀自动机)
求多串的最长公共字串.法1: 二分长度+hash 传送门法2: 二分+后缀数组 传送门法3: 后缀自动机拿第一个串建自动机,然后用其他串在上面匹配.每次求出SAM上每个节点的最长匹配长度后,再在全局取最小值(因为是所有串的公共串)就行了.CODE#include<bits/stdc++.h&g...