2020-2021:teams:legal_string:jxm2001:other:错题集_3
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:other:错题集_3 [2020/08/27 20:16] jxm2001 |
2020-2021:teams:legal_string:jxm2001:other:错题集_3 [2020/08/31 18:12] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 541: | 行 541: | ||
| } | } | ||
| enter(1LL*ans*ans%Mod); | enter(1LL*ans*ans%Mod); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== 7、B-Suffix Array ===== | ||
| + | |||
| + | [[https://ac.nowcoder.com/acm/contest/5666/A|链接]] | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给出一个字符串，定义一个字符串 $S$ 对应序列 $B$，其中 $b_i=\min_{j\lt i,s_j=s_i} (i-j)$，如果不存在 $j$，$b_i=0$。 | ||
| + | |||
| + | 求序列 $B$ 后缀排序后的结果。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 构造 $c_i=\min_{j\gt i,s_j=s_i}(j-i)$，如果不存在 $j$，$b_i=n$。特别的，$c_{n+1}$ 为 $c$ 的结束符且 $c_{n+1}=n+1$。 | ||
| + | |||
| + | 有结论将 $B$ 序列后缀排序结果翻转后与 $C[1,n+1]$ 后缀排序前 $n$ 项相同。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | #include <cstdio> | ||
| + | #include <algorithm> | ||
| + | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| + | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| + | #define mem(a,b) memset(a,b,sizeof(a)) | ||
| + | using namespace std; | ||
| + | typedef long long LL; | ||
| + | const int MAXN=1e5+5; | ||
| + | namespace SA{ | ||
| + | int sa[MAXN],x[MAXN],y[MAXN],c[MAXN]; | ||
| + | void get_sa(int *s,int n,int m){ | ||
| + | _rep(i,0,m)c[i]=0; | ||
| + | _rep(i,1,n)c[x[i]=s[i]]++; | ||
| + | _rep(i,1,m)c[i]+=c[i-1]; | ||
| + | for(int i=n;i;i--)sa[c[x[i]]--]=i; | ||
| + | for(int k=1;k<n;k<<=1){ | ||
| + | int pos=0; | ||
| + | _rep(i,n-k+1,n)y[++pos]=i; | ||
| + | _rep(i,1,n)if(sa[i]>k)y[++pos]=sa[i]-k; | ||
| + | _rep(i,0,m)c[i]=0; | ||
| + | _rep(i,1,n)c[x[i]]++; | ||
| + | _rep(i,1,m)c[i]+=c[i-1]; | ||
| + | for(int i=n;i;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0; | ||
| + | _rep(i,1,n)swap(x[i],y[i]); | ||
| + | pos=0,y[n+1]=0; | ||
| + | _rep(i,1,n)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?pos:++pos; | ||
| + | if(pos==n)break; | ||
| + | m=pos; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | char buf[MAXN]; | ||
| + | int a[MAXN],last[2]; | ||
| + | int main() | ||
| + | { | ||
| + | int n; | ||
| + | while(~scanf("%d%s",&n,buf+1)){ | ||
| + | last[0]=last[1]=0; | ||
| + | for(int i=n;i;i--){ | ||
| + | int c=buf[i]-'a'; | ||
| + | if(last[c])a[i]=last[c]-i; | ||
| + | else a[i]=n; | ||
| + | last[c]=i; | ||
| + | } | ||
| + | a[n+1]=n+1; | ||
| + | SA::get_sa(a,n+1,n+1); | ||
| + | for(int i=n;i;i--) | ||
| + | printf("%d ",SA::sa[i]); | ||
| + | puts(""); | ||
| + | } | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/other/错题集_3.1598530616.txt.gz · 最后更改: 2020/08/27 20:16 由 jxm2001
