后缀数组 顾名思义.SuffixArray(下面有时简称SA) 和字符串的后缀有关. 后缀:字符串中某个位置一直到结尾的子串.(SA中讨论包含了原串和空串).所以共同拥有len+1个后缀. 后缀数组: 字符串的全部后缀组成的按字典序从小到大排好的数组.因为SA中记录的都是字符串的后缀,所以SA仅仅须要记录其表示的后缀的起始位置. 因为比較字典序是O(n)的,所以暴力算法的复杂度将是O(n^2logn).通过一些算法能够降到线性复杂度.这里先介绍一种简单的O(nlognlogn)的算法. 该算法的

[题目分析] 判断有多少个长度不小于k的相同子串的数目. N^2显然是可以做到的. 其实可以维护一个关于height的单调栈,统计一下贡献,就可以了. 其实还是挺难写的OTZ. [代码] #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <map> #include <set> #include <queue>

[题目分析] 其实找最长的不重叠字串是很容易的,后缀数组+二分可以在nlogn的时间内解决. 但是转调是个棘手的事情. 其实只需要o(*￣▽￣*)ブ差分就可以了. 背板题. [代码] #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <map> #include <set> #include <queue> #

3230: 相似子串 Time Limit: 20 Sec  Memory Limit: 128 MBSubmit: 1485  Solved: 361[Submit][Status][Discuss] Description Input 输入第1行,包含3个整数N,Q.Q代表询问组数.第2行是字符串S.接下来Q行,每行两个整数i和j.(1≤i≤j). Output 输出共Q行,每行一个数表示每组询问的答案.如果不存在第i个子串或第j个子串,则输出-1. Sample Input 5 3 aba

后缀数组+莫比乌斯函数 #include <stdio.h> #include <string.h> #include<algorithm> using namespace std; ; const int MAXN = N; //数列的最大值和个数上界 struct SuffixArray{ int wa[MAXN]; //用来进行基数排序或临时变量 int wb[MAXN]; //用来进行基数排序或临时变量 int wv[MAXN]; //用来进行基数排序或临时变量

一些定义:设字符串S的长度为n,S[0~n-1]. 子串:设0<=i<=j<=n-1,那么由S的第i到第j个字符组成的串为它的子串S[i,j]. 后缀:设0<=i<=n-1,那么子串S[i,n-1]称作它的后缀,用Suffix[i]表示. 串比较:对于两个串S1,S2,设长度分别为n1,n2.若存在一个位置i,使得对于0<=j<i满足S1[j]=S2[j]且S1[i]<S2[i],那么我们称S1<S2.如果S1是S2的一个前缀,那么也有S1<S2

后缀数组,看到网上很多题解都是单调栈,这里提供一个不是单调栈的做法, 首先将两个串 连接起来求height   求完之后按height值从大往小合并.  height值代表的是  sa[i]和sa[i-1] 的公共前缀长度,那么每次合并就是合并  i和i-1 那么在合并小的时候公共前缀更大的肯定已经都合并在一起,那么就可以直接统计了. #include<iostream> #include<cstdio> #include<algorithm> #include<

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5442 题目大意:给你一个长度为n的字符串,将它首尾相连成环.问你这个环上找一个长度为n的字典序最大的串(你可以沿顺时针或逆时针找),如果有多个这样的串,输出首字母标号最小的,如果还有多个,输出顺时针的 解: 1.最小表示法解(时间复杂度:O(n)) 最小表示法~ 2.后缀数组(时间复杂度:O(logn)) 比赛的时候想到的方法,然而并没有写出来,不好写+高时间复杂度=不推荐 最小表示法: /* *

后缀数组很久很久以前就出现了,具体的概念读者自行搜索,小菜仅略知一二,不便讨论. 本文通过寻找两个字符串的最长公共子字符串,演示了后缀数组的经典应用. 首先需要说明,小菜实现的这个后缀数组算法,并非标准,只是借鉴了其中的思想. 小菜实现的算法,有两个版本,第一个是空间换时间,第二个是时间换空间. 空间换时间版本 /* 利用后缀数组获取两个字符串最长公共子字符串 空间换时间版本 @params s1 String,要分析的字符串 s2 String,要分析的字符串 norepeat Boolean

JScript 代码   复制 (function($){ $.fn.emailMatch= function(settings){ var defaultSettings = { emailTip:"请输入邮箱地址", aEmail: ["163.com", "qq.com", "gmail.com", "126.com", "hotmail.com", "yahoo.com

题意:给出一个字符串,长度是2*10^4.将它首尾相接形成环,并在环上找一个起始点顺时针或逆时针走一圈,求字典序最大的走法,如果有多个答案则找起始点最小的,若起始点也相同则选择顺时针. 分析:后缀数组. 首先,需要补充后缀数组的基本知识的话,看这个链接. http://www.cnblogs.com/rainydays/archive/2011/05/09/2040993.html 我利用这道题重新整理了后缀数组的模板如下: ; //call init_RMQ(f[], n) first. //

Dr. Ellie Arroway has established contact with an extraterrestrial civilization. However, all efforts to decode their messages have failed so far because, as luck would have it, they have stumbled upon a race of stuttering aliens! Her team has found

如果不存在模糊点,那么答案就是两个串的最长公共子串. 如果模糊点是某个串的开头或者结尾,那么可以暴力枚举另一个串中的某个前后缀更新答案. 否则,假设模糊点在第一个串里是$i$,在第二个串里是$j$,那么此时对答案的贡献为$lcp(i+1,j+1)+lcs(i-1,j-1)+1$. 将两个串用特殊字符拼接,求出正串的后缀数组以及反串的后缀数组,那么$lcp(i+1,j+1)+lcs(i-1,j-1)+1$等价于两个height数组的区间最小值的和. 考虑从大到小枚举第一个数,每次把所有大于等于它的

后缀数组+单调栈 代码 #include<cstdio> #include<algorithm> #include<cstring> using namespace std; ; const int MAXN = N; struct SuffixArray{ int wa[MAXN]; int wb[MAXN]; int wv[MAXN]; int ws[MAXN]; int sa[MAXN]; int rank[MAXN]; int height[MAXN]; int

虽然这个队,以后再也没有了,但是他的模板,是永垂不朽的![误 #include <ext/pb_ds/priority_queue.hpp> __gnu_pbds::priority_queue < int > Q; 优先队列,配对堆默认,从小到大! __gnu_pbds::priority_queue < int , greater < int > , pairing_heap_tag > Q; __gnu_pbds::priority_queue <

首先求出后缀数组,得到本质不同的子串的个数. 然后二分答案,每次先通过后缀数组求出第$mid$小的子串,然后贪心进行检验. 检验的时候,从后往前贪心,每次加入一个后缀,如果不能加了,那就划为一段. 时间复杂度$O(n\log n)$. #include<cstdio> #include<cstring> #include<algorithm> #define N 100010 using namespace std; typedef long long ll; char

枚举$B$串的每个后缀,统计出该后缀所有满足条件的前缀. 考虑暴力搜索,设状态$(x,y,z)$表示当前需要考虑$A$从$x$开始的后缀,$B$从$y$开始的后缀,之前部分编辑距离为$z$. 那么首先用后缀数组+ST表求出两个后缀的lcp,$x$和$y$都可以向右跳那么多,且不产生任何代价. 如果此时匹配到了底,那么可以得到在一段区间$[L,R]$内,所有前缀都是合法的.注意到这种前缀只有$2K+1$种,所以可以使用差分前缀和来进行标记. 如果还没有匹配到底,那么有$3$种选择,分别是状态$(x

将S1与S2用#号拼接在一起形成S串 将S3与S串跑KMP求出S3在S串中每次出现的位置l[i] 对于S串每个后缀i,求出f[i]表示该串不包含S3串的最长前缀 然后求出S串的后缀数组 先从小到大扫描后缀数组, 同时维护一个tmp表示S2中的串与现在的串的最长公共前缀,且没有出现S3, 如果碰到一个S1的后缀,那么更新ans=max(ans,min(f[sa[i]],tmp)) 如果碰到一个S2的后缀,那么更新tmp=max(tmp,f[sa[i]]) 然后将tmp与height取一个最小值 最

后缀数组搞一下就可以了喵~ 其实这道题的第一个想法是 SAM ,建完后缀自动机后拓扑排序跑一遍统计下每个子串的出现次数就 O(N) 就妥妥过掉了 后缀树也是 O(N) 的,统计一下每个节点对应的子树中有多少个叶子节点即可 可是看了一下数据范围,欸呦你妹啊,字符数 1000000+1 是什么心态啊!居然把我的后缀树和后缀 zdj 都卡掉了啊! 然后很痛苦的想了想后缀数组的做法: 搞出 sa, rank, height 三个数组后,跑一遍二分,用一个 tot 表示找到了几个子串 二分答案 L,O(N

----------------------------------------------------------------------------------------------------------- 程序包标准类库 其他程序包     子库     社区标准类库 名称     摘要 存档            tar     tar包实现了对档案的压缩.      zip     zip程序包对读写ZIP文档提供支持. bufio     bufio包实现了输入/输出缓冲.它包含

练习一下字符串,做一下这道题. 首先是关于一个字符串有多少不同子串的问题,串由小到大排起序来应该是按照sa[i]的顺序排出来的产生的. 好像abbacd,排序出来的后缀是这样的 1---abbacd     第一个串产生的6个前缀都是新的子串 2---acd          第二个串除了和上一个串的前缀1 3-1=2 产生了2个子串 3---bacd        4-0=4 4---bbacd      5-1=4 5---cd           2-0=0 6---d