題目大意：求嚴格/非嚴格K小子串
首先建立Sam
然後BFS一遍求出每個點代表狀態的出現次數
此時如果是嚴格的那麼每個點代表狀態的出現次數都應該是1
然後DFS一遍求出每個節點的後繼狀態個數
然後就隨便搞了啊= =
媽了個雞卡常數。。。
#include
#include
#include
#include
#define M 500500
using 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
