标签为 [后缀数组] 的文章

后缀数组:从入门到不会

其实我也不是很会这种玄学的东西。。。 不过这东西貌似可以支持很多字符串操作。。。 求一个字符串中本质不同子串的数量  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- ......