题解 P3975 【[TJOI2015]弦论】

xzyxzy

2018-06-15 21:53:55

Solution

如果你还不懂SAM,请点击[blog](https://www.cnblogs.com/xzyxzy/p/9186759.html) 构建出$SAM$之后,求出$sum[i]$,表示有$sum[i]$个子串经过$i$号点 $siz[i]$表示$i$所代表的$Endpos$的集合大小,也就是$i$所对应字符串集合的出现次数 $T=0$时,本质相同的子串在不同位置出现算相同,所以$siz[i]=1$,即将每个字符串集合的$Endpos$集合大小(字符串集合元素出现次数)置为$1$ $T=1$时,本质相同的子串在不同位置出现算不同,那么累加后的$siz$表示实际上$Endpos$的集合大小 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define ll long long using namespace std; const int N=1100000; char s[N]; int fa[N],len[N],siz[N],ch[N][26]; int t[N],A[N]; ll sum[N],K; int l,lst=1,node=1,T; void Extend(int c) { int f=lst,p=++node;lst=p; len[p]=len[f]+1;siz[p]=1; while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f]; if(!f) {fa[p]=1;return;} int x=ch[f][c],y=++node; if(len[x]==len[f]+1) {fa[p]=x;node--;return;} memcpy(ch[y],ch[x],sizeof(ch[y])); len[y]=len[f]+1; fa[y]=fa[x]; fa[x]=fa[p]=y; while(f&&ch[f][c]==x) {ch[f][c]=y;f=fa[f];} } void Print(int x,int k) { if(k<=siz[x]) return; k-=siz[x]; for(int i=0;i<26;i++) { int R=ch[x][i]; if(!R) continue; if(k>sum[R]) {k-=sum[R];continue;} putchar(i+'a');Print(R,k);return; } } int main() { //Part 1 Build SAM scanf("%s%d%lld",s,&T,&K);l=strlen(s); for(int i=l;i>=1;i--) s[i]=s[i-1];s[0]=0; for(int i=1;i<=l;i++) Extend(s[i]-'a'); //Part 2 Sort for(int i=1;i<=node;i++) t[len[i]]++; for(int i=1;i<=node;i++) t[i]+=t[i-1]; for(int i=1;i<=node;i++) A[t[len[i]]--]=i; for(int i=node;i>=1;i--) siz[fa[A[i]]]+=siz[A[i]]; for(int i=1;i<=node;i++) T==0?(sum[i]=siz[i]=1):(sum[i]=siz[i]); siz[1]=sum[1]=0; /* 这一段代码调试了半个小时 前者是对自动机处理(自动机上累加求的是子串个数) 后者是parent树(parent树上累加求的是i节点对应的endpos的字符集的longest的出现次数) */ for(int i=node;i>=1;i--) for(int j=0;j<26;j++) if(ch[A[i]][j]) sum[A[i]]+=sum[ch[A[i]][j]]; // for(int i=node;i>=1;i--) sum[fa[A[i]]]+=sum[A[i]]; if(sum[1]<K) puts("-1"); else Print(1,K),puts(""); return 0; } ``` ~~经过进一步的学习发现之前的题解不够清晰,Upd:6.16~~