回文树&后缀自动机&后缀数组
KMP，扩展KMP和Manacher就不写了，感觉没多大意思。 之前感觉后缀自动机简直可以解决一切，所以不怎么写后缀数组。 马拉车主要是通过对称中心解决问题，有的时候要通过回文串的边界解决问题，这个时候回文树就用到了，又好写，又强大。 之前整理过一篇后缀自动机的。感觉还要整理一下，顺便把回文树，后缀...
POJ 2774 (后缀数组 最长公共字串) Long Long Message
用一个特殊字符将两个字符串连接起来，然后找最大的height，而且要求这两个相邻的后缀的第一个字符不能在同一个字符串中。 #include <cstdio> #include <cstring> #include <algorithm> using namespa...
后缀数组 (Suffix Array) 学习笔记
\(\\\)定义介绍一些写法和数组的含义，首先要知道 字典序 。\(len\)：字符串长度\(s\)：字符串数组，我们的字符串存储在 \(s[0]...s[len-1]\) 中。\(suffix(i) ,i\in[0,len-1]\)： 表示子串 \(s[i]...s[len-1]\)，即从 \(i...
笔试算法题（40）：后缀数组 & 后缀树（Suffix Array & Suffix Tree）
议题：后缀数组(Suffix Array)分析：后缀树和后缀数组都是处理字符串的有效工具，前者较为常见，但后者更容易编程实现，空间耗用更少；后缀数组可用于解决最长公共子串问题，多模式匹配问题，最长回文串问题，全文搜索等问题；后缀数组的基本元素：给定一个string，其长度为L，后缀指的是从strin...
基于后缀数组的字符串匹配
#include<bits/stdc++.h>using namespace std;const int MAX_N=1000005;int n,k;int Rank[MAX_N+1];int tmp[MAX_N+1];int sa[MAX_N+1];bool compare_sa(in...
[BZOJ4278][ONTAK2015]Tasowanie（后缀数组+贪心）
题目描述 传送门 题解 和队列变换那道题差不多 就是将两个串连起来求一个sa，然后归并的时候如果两个数相等的话就拿后缀字典序比较小的那一个 第一个串的结尾和第二个串的结尾要加一个比较大的字符，因为如果两个串比较前面的很多都相等的话，应该排除最后一位的影响，选比较多的一个串 代码 #...
数据结构4——后缀数组
一、相关介绍 后缀数组 处理字符串的有力工具 可以处理后缀自动机解决不了的问题 后缀数组被称为SA，后缀自动机被称为SAM 。 更详细的讲解点击...
poj 2406 Power Strings 后缀数组解法
连续重复子串问题poj 2406 Power Stringshttp://poj.org/problem?id=2406问一个串能否写成a^n次方这种形式。虽然这题用kmp做比较合适，但是我们还是用后缀数组做一做，巩固后缀数组的能力。对于一个串，如果能写出a^n这种形式，我们可以暴力枚举循环节长度L...
2018.11.24 poj3415Common Substrings（后缀数组+单调栈）
传送门常数实在压不下来（蒟蒻开O(3)都过不了）。但有正确性233.首先肯定得把两个字符串接在一起。相当于heightheightheight数组被height<kheight<kheight<k的分成了几段，统计每段的贡献。考虑段中每个heightheighthe...
Trie vs.后缀树vs.后缀数组
Which structure provides the best performance results; trie (prefix tree), suffix tree or suffix array? Are there other similar structures? What are g...
[置顶] 后缀数组练习题（转）
原文：http://hi.baidu.com/lewutian/blog/item/4d098138d29c34f9b311c725.html 接下来逐步A掉里面的题。 贴个DC3的模版。 /****后缀数组模版****/#define F(x)((x)/3+((x)%3==1?0:tb)) /...
HDOJ 题目3518 Boring counting（后缀数组，求不重叠反复次数最少为2的子串种类数）
Boring countingTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 2253 Accepted Submission(s):...
BZOJ_2754__[SCOI2012]_喵星球上的点名_(暴力+后缀数组)
描述http://www.lydsy.com/JudgeOnline/problem.php?id=2754给出n个姓名串和m个点名串.求每个点名串在多少人的姓名中出现过(在名中出现或在姓中出现,不能跨越),以及最后每个人被点到多少次.分析这种解法是用后缀数组优化一下暴力,(优化了吗?)复杂度并不能...
[后缀数组 贪心] BZOJ 4278 [ONTAK2015]Tasowanie
两个指针 显然小的那个先放 如果一样 比后一个 再一样 再后 然后就转化成比较后缀的字典序了 #include<cstdio>#include<cstdlib>#include<algorithm>using namespace std;inline cha...
HDU 5442 2015长春站网络赛1006（后缀数组）
后缀数组大神模板 比赛的时候没有A掉的一题，总结起来还是自己想得过于简单了，实际上也确实是蛮简单的裸地后缀数组的题（好像正解不是后缀数组写的）。 做法是：正着再写一边,找一次sa[2n-1], 这个就是对应的顺时针最优解。把序列翻转以后再写一边，照一次sa[2n-1]，算出所有height值，逆序再...
poj3693之后缀数组
Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 5946 Accepted: 1799DescriptionThe repetition number of a string is defined as the maximum nu...
[AHOI2013] 差异 - 后缀数组,单调栈
[AHOI2013] 差异Description求 \(\sum {len(T_i) + len(T_j) - 2 lcp(T_i,T_j)}\) 的值其中 \(T_i (i = 1,2,...,n)\) 为后缀串 \(S[i,n]\)Solution单调栈乱扫一发即可。始终维护当前栈内元素的和，然...
HDU 5769 Substring 后缀数组
SubstringProblem Description?? is practicing his program skill, and now he is given a string, he has to calculate the total number of its distinct sub...
poj 3261 Milk Patterns 后缀数组 + 二分
题目链接题目描述给定一个字符串，求至少出现 \(k\) 次的最长重复子串，这 \(k\) 个子串可以重叠。思路二分 子串长度，据其将 \(h\) 数组 分组，判断是否存在一组其大小 \(\geq k\).Code#include <cstdio>#include <vector&g...
Java后缀数组之求sa数组的实例代码
后缀数组就是一个字符串所有后缀大小排序后的一个集合，然后我们根据后缀数组的一些性质就可以实现各种需求。这篇文章主要介绍了Java后缀数组-求sa数组,需要的朋友可以参考下