后缀自动机这个神仙算法已经搞了好久了
一次又一次的从入门到放弃
直到这段时间发现躲不过去了 只好强行学习
发现这道题很不错 既询问了本质不同的第k大子串 也询问了位置不同的第k大子串 值得记录
代码都是自动机的常规操作 可以作为知识点记下来
#include<bits/stdc++.h> using namespace std; const int maxn=5e5+5; char s[maxn]; int siz[maxn*2],val[maxn*2]; int n,op,k; struct Suffix_Automation { int next[maxn*2][26],fa[maxn*2],l[maxn*2]; int last,cnt; int cntA[maxn*2],A[maxn*2]; void init() { last=cnt=1; fa[1]=l[1]=0; memset(next[1],0,sizeof next[1]); } int inline newnode() { cnt++; memset(next[cnt],0,sizeof next[cnt]); fa[cnt]=l[cnt]=0; return cnt; } void add(int c) { int p=last; int np=newnode(); l[np]=l[p]+1; val[np]=1; last=np; while(p&&!next[p][c]) next[p][c]=np,p=fa[p]; if(!p) fa[np]=1; else { int q=next[p][c]; if(l[q]==l[p]+1) fa[np]=q; else { int nq=++cnt; l[nq]=l[p]+1; memcpy(next[nq],next[q],sizeof next[q]); fa[nq]=fa[q]; fa[np]=fa[q]=nq; while(next[p][c]==q) next[p][c]=nq,p=fa[p]; } } } void work() { memset(cntA,0,sizeof cntA); for(int i=1;i<=cnt;i++) cntA[l[i]]++; for(int i=1;i<=n;i++) cntA[i]+=cntA[i-1]; for(int i=1;i<=cnt;i++) A[cntA[l[i]]--]=i; for(int i=cnt;i>=1;i--) { int p=A[i]; if(op==1) val[fa[p]]+=val[p]; else val[p]=1; } val[1]=0; for(int i=cnt;i>=1;i--) { int p=A[i]; siz[p]=val[p]; for(int j=0;j<26;j++) siz[p]+=siz[next[p][j]]; } } void dfs(int x,int k) { if(k<=val[x]) return ; k-=val[x]; for(int i=0;i<26;i++) { int t=next[x][i]; if(t) { if(k<=siz[t]) { printf("%c",'a'+i); dfs(t,k); return ; } k-=siz[t]; } } } }sam; int main() { scanf("%s",s+1); n=strlen(s+1); sam.init(); for(int i=1;i<=n;i++) sam.add(s[i]-'a'); scanf("%d%d",&op,&k); sam.work(); if(k>siz[1]) printf("-1"); else sam.dfs(1,k); printf("\n"); return 0; }
