2020-2021:teams:legal_string:jxm2001:字符串_3
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:字符串_3 [2020/08/31 18:17] jxm2001 |
2020-2021:teams:legal_string:jxm2001:字符串_3 [2020/09/02 10:52] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== 字符串 3 ====== | ====== 字符串 3 ====== | ||
| - | ===== 后缀数组 ===== | + | ===== 后缀数组(SA) ===== |
| ==== 算法简介 ==== | ==== 算法简介 ==== | ||
| 行 43: | 行 43: | ||
| int sa[MAXN],rk[MAXN],height[MAXN],X[MAXN],Y[MAXN],c[MAXN]; | int sa[MAXN],rk[MAXN],height[MAXN],X[MAXN],Y[MAXN],c[MAXN]; | ||
| int d[MAXN][MAXM],lg2[MAXN]; | int d[MAXN][MAXM],lg2[MAXN]; | ||
| - | void get_sa(int *s,int n,int m){//s下标从1开始 | + | void get_sa(char *s,int n,int m){//s下标从1开始 |
| int *x=X,*y=Y; | int *x=X,*y=Y; | ||
| _rep(i,0,m)c[i]=0; | _rep(i,0,m)c[i]=0; | ||
| 行 63: | 行 63: | ||
| m=pos; | m=pos; | ||
| } | } | ||
| + | _rep(i,1,n)rk[sa[i]]=i; | ||
| } | } | ||
| void get_height(char *s,int n){//必须先得到sa数组和rk数组 | void get_height(char *s,int n){//必须先得到sa数组和rk数组 | ||
2020-2021/teams/legal_string/jxm2001/字符串_3.1598869056.txt.gz · 最后更改: 2020/08/31 18:17 由 jxm2001
