解题思路

　　首先建\(sam\)，然后在拓扑序上\(dp\)一下，把每个点的路径数算出来，然后统计答案时就在自动机上\(dfs\)一下，仿照平衡树那样找第\(k\)小。

代码

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int MAXN = 90005;inline int rd(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();    return f?x:-x;}int n,Q,l[MAXN<<1],fa[MAXN<<1],ch[MAXN<<1][27];int lst,cnt,f[MAXN<<1],c[MAXN<<1],a[MAXN<<1];char s[MAXN];inline void Insert(int c){    int p=lst,np=++cnt;lst=np;l[np]=l[p]+1;    for(;p && !ch[p][c];p=fa[p]) ch[p][c]=np;    if(!p) fa[np]=1;    else {        int q=ch[p][c];        if(l[q]==l[p]+1) fa[np]=q;        else{            int nq=++cnt;l[nq]=l[p]+1;            memcpy(ch[nq],ch[q],sizeof(ch[q]));            fa[nq]=fa[q];fa[q]=fa[np]=nq;            for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;        }    }} void query(int x){    int p=1;    while(x){        for(int i=1;i<=26;i++)if(ch[p][i]){            if(f[ch[p][i]]