题目大意：求严格/非严格K小子串
首先建立Sam
然后BFS一遍求出每个点代表状态的出现次数
此时如果是严格的那么每个点代表状态的出现次数都应该是1
然后DFS一遍求出每个节点的后继状态个数
然后就随便搞了啊= =
妈了个鸡卡常数，
BZOJ 3998 TJOI2015 弦论 后缀自动机
。。。<code class="language-c++ hljs perl">#include<cstdio>#include<cstring>#include<iostream>#include #define M 500500using namespace std;int type,k;char s[M],ans[M];int tot;namespace Suffix_Automaton{ struct Sam{ Sam *son[26],*parent; int max_dpt,cnt; long long size; int v; void* operator new (size_t,int _) { static Sam mempool[M<<1],*C=mempool; C->max_dpt=_; return C++; } }*root=new (0)Sam,*last=root; void Extend(int x) { Sam *p=last; Sam *np=new (p->max_dpt+1)Sam; for(;p&&!p->son[x];p=p->parent) p->son[x]=np; if(!p) np->parent=root; else { Sam *q=p->son[x]; if(p->max_dpt+1==q->max_dpt) np->parent=q; else { Sam *nq=new (p->max_dpt+1)Sam; memcpy(nq->son,q->son,sizeof nq->son); nq->parent=q->parent; q->parent=nq;np->parent=nq; for(;p&&p->son[x]==q;p=p->parent) p->son[x]=nq; } } last=np; } void BFS() { static Sam *q[M<<1]; int i,r=0,h=0; q[++r]=root; while(r!=h) { Sam *p=q[++h]; for(i=0;i<26;i++) if(p->son[i]&&p->son[i]->v!=1) p->son[i]->v=1,q[++r]=p->son[i]; } for(i=r;i>=2;i--) { Sam *p=q[i]; if(type==0) p->cnt=(bool)p->cnt; p->parent->cnt+=p->cnt; } } void DFS(Sam *p) { int i; p->v=2; p->size=p->cnt; for(i=0;i<26;i++) if(p->son[i]) { if(p->son[i]->v!=2) DFS(p->son[i]); p->size+=p->son[i]->size; } } void Get_Kth(Sam *p,int k) { int i; if(k<=p->cnt) return ; k-=p->cnt; for(i=0;i<26;i++) if(p->son[i]) { if(k<=p->son[i]->size) { ans[++tot]=i+'a'; Get_Kth(p->son[i],k); return ; } k-=p->son[i]->size; } }}int main(){ using namespace Suffix_Automaton; int i; scanf("%s%d%d",s+1,&type,&k); for(i=1;s[i];i++) { Extend(s[i]-'a'); last->cnt++; } BFS();root->cnt=0; DFS(root); if(root->size<k) code="" return=""></k)></iostream></cstring></cstdio></code>