[TJOI2015]弦论

ゝ一世哀愁。 2021-11-01 09:56 241阅读 0赞

[Link][]

--------------------

很经典的一道后缀自动机裸体

我们首先不考虑题目中的两种情况，只考虑如何输出第k大的字串。很显然，有一个性质，**首位字符越大，字串排名越靠后**，我们可以考虑一个字符一个字符地去枚举（在后缀自动机上跑，字符必须存在），若第k大的子串是以当前字符开头的，那么就往下走，否则就继续枚举下一个字符，再减去以这个字符开头的子串个数。也就是说，我们现在的问题变成了统计以后缀自动机上某一个节点开头的子串的个数，这个问题就很简单了。

### 先说T=0 ###

我们回归right集合的本质，它表示的是结束位置相同的子串集合，那么right集合的大小就表示当前结束位置相同的子串的个数，等价于当前已经匹配到的字符串的出现次数。因为相同子串只算一次，所以直接把所有的right集合大小赋值为1即可。

### T=1 ###

同T=0，直接建出Parent树，在树上dfs一遍求出所有right集合大小（当然还可以倒序for一遍，因为是一棵树，不会有后效性）

但求出了right集合大小还是不够的，我们需要考虑另外一个数组sum，表示的是right集合在后缀自动机意义下的前缀和，sum\[u\]就表示以一个后缀自动机上，编号为u的节点作为前缀的子串个数（同文章开头待求的值）。因为后缀自动机建出来是一个DAG，所以可以使用拓扑排序（本人用的是记忆化深搜）

但这样似乎会比其他几位dalao用的基排会慢一些（可能是递归的原因）

还是见代码吧（里面有注释）

#include<stdio.h> #include<string.h> #define rint register int #define N 2000007 template<class T> inline void read(T &x){ x=0;char c=getchar();T flag=1; while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();} x*=flag; } struct E{ int next,to; }e[N]; struct Node{//SAM int c[27],len,par; }nd[N]; char s[N]; int n,tot=1,root=1,last=1,head[N],cnt=0,opt; long long right[N],sum[N],rk; inline int max(int x,int y){return x>y? x:y;} inline void add(int id,int to){ e[++cnt]=(E){head[id],to}; head[id]=cnt; } inline void insert(int w){ int tmp=last,X=last=++tot;right[tot]=1; nd[X].len=nd[tmp].len+1; for(;tmp&&!nd[tmp].c[w];tmp=nd[tmp].par) nd[tmp].c[w]=X; if(!tmp) nd[X].par=root; else{ int B=nd[tmp].c[w]; if(nd[B].len==nd[tmp].len+1) nd[X].par=B; else{ int nb=++tot; nd[nb]=nd[B]; nd[B].par=nd[X].par=nb; nd[nb].len=nd[tmp].len+1; for(;tmp&&nd[tmp].c[w]==B;tmp=nd[tmp].par) nd[tmp].c[w]=nb; } } } void dfs(int u){ if(!opt) right[u]=1;//若T=0，right赋为1 for(int i=head[u];i;i=e[i].next){ int v=e[i].to; dfs(v); if(opt) right[u]+=right[v];//否则就问子树里right的和 } } int dfs_(int u){ if(sum[u]!=-1) return sum[u]; sum[u]=right[u]; for(int i=0;i<26;i++) if(nd[u].c[i]) sum[u]+=dfs_(nd[u].c[i]); return sum[u]; } void print(int u,long long k){ if(k<=right[u]) return; k-=right[u]; //排名大于当前字符串的个数，说明还没匹配完，应该减去 for(int i=0;i<26;i++)//枚举每个字符 if(nd[u].c[i]){//若字符存在 int v=nd[u].c[i]; if(k>sum[v]){//不是以当前字符开头 k-=sum[v]; continue; } printf("%c",i+'a');//匹配到 print(v,k);//匹配下一位 return; } } int main(){ scanf("%s",s); read(opt),read(rk); n=strlen(s); memset(sum,-1,sizeof(sum)); for(rint i=0;i<n;++i) insert(s[i]-'a'); for(rint i=2;i<=tot;++i) add(nd[i].par,i);//建Parent树 dfs(1);//求right集合大小 right[1]=0; dfs_(1);//求前缀和（注意是在后缀自动机上） if(sum[1]<rk) printf("-1");//如果子串总个数小于需要查的排名，则输出无解 else print(1,rk);//输出排名为rk的字符串 }

转载于:https://www.cnblogs.com/wwlwQWQ/p/11226604.html

[Link]: https://www.luogu.org/problemnew/show/P3975