分类: [后缀数组]

bzoj 3238 差异

题目传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=3238 后缀数组+单调队列 这是一道后缀数组的模板题。 简单来说,就是先用后缀数组求出h数组。 然后利用单调队列在o(n)的时间复杂度下求出任意两个后缀的最大公共前缀长度的和。 大家看代码理解吧。 #include<cstdio> #include<algorithm> #include<cstring> using namespace std; long long ans; char st[510000]; int sum[510000],c[510000],h[510000],sa[2][510000],rk[2][510000]; in ......

后缀数组:从入门到不会

其实我也不是很会这种玄学的东西。。。 不过这东西貌似可以支持很多字符串操作。。。 求一个字符串中本质不同子串的数量  SPOJ Disubtr 先预处理出后缀数组,然后求出将后缀排完序后的相邻两个后缀的LCP, $Ans=\sum n-sa[i]-h[i]$ #include<bits/stdc++.h> using namespace std; char ch[1000000]; int x[1000000],y[1000000],sa[1000000]; int n,m,c[1000000],l,rank[1000000],h[1000000]; int main() { int cas; scanf("%d",&cas); while (cas--) { memset(c,0,siz ......

UOJ35 后缀排序

题目传送门 这是一个后缀数组模板题 似乎没有什么好说的,直接上代码。。 #include&lt;cstdio&gt; #include&lt;cmath&gt; #include&lt;cstdlib&gt; #include&lt;cstring&gt; #include&lt;algorithm&gt; using namespace std; int n,pre,now,k,a[100005],sa[2][100005],h[100005],rk[2][100005],v[100005]; char ch[100005]; void work(int *sa,int *rk,int *SA,int *RK){ for(int i=1;i&lt;=n;i++) v[rk[sa[i]]]=i; for(int i=n;i;i- ......