注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

后缀树模板题  

2012-10-05 15:55:14|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
510(伍一鸣)的题,后缀树模板题
我的代码是经过与510高同步所得
可见于115上的wc2012 by 510

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

const int MAX=3000000+10;
const int ALPHA=30;

int n;
char str[MAX];
int pt[1<<15];

struct Node;

struct Edge
{
int l,r;
Node* t;
Edge(){t=0;}

void modify(int ll,int rr,Node* next)
{
l=ll;
r=rr;
t=next;
}
}eg[MAX];
int tote;

struct Node
{
Edge* e[ALPHA];
Node* slink;
int dep,exi,time;
Node(){slink=0;memset(e,0,sizeof e);dep=exi=0;}

void add(int num,int l,int r,Node* next)
{
e[num]=eg+(tote++);
e[num]->modify(l,r,next);
exi|=(1<<num);
}

void modify(int num,int l,int r,Node*next)
{
e[num]->modify(l,r,next);
}
}*Root,*Seed,p[MAX];
int tot;

void PreSuffixTree()
{
tot=0;
Seed=p+(tot++);
Root=p+(tot++);
Root->slink=Seed;
for(int i=0;i<=26;++i)
Seed->add(i,0,0,Root);
}

Edge* q[MAX];
int numq;

int getnum(int u)
{
if(u>(1<<14))return pt[u>>14]+14;
else return pt[u];
}

void show(Node* u)
{
int tot=0,j=u->exi,i=getnum(j&(-j));
for(j=u->exi;j;j-=(j&(-j)))
{
i=getnum(j&(-j));
if(u->e[i])
{
++tot;
q[++numq]=u->e[i];
show(u->e[i]->t);
--numq;
}
}
if(!tot)
{
int i;
for(i=1;i<=numq;++i)
printf("%d %d ",q[i]->l,q[i]->r);
printf("\n");
}
}

void BuildSuffixTree(char * str,int n)
{
PreSuffixTree();
int i,k=1,id,tnum;
Node* now=Root;
for(i=0;i<=14;++i)
pt[1<<i]=i;
for(i=1;i<=n;++i)
{
id=str[i];
Node *old=Root,*np;
while(1)
{
while(k<i)
{
tnum=str[k];
Edge* ep=now->e[tnum];
if(k+ep->r-ep->l+1<=i)
{
k+=ep->r-ep->l+1;
now=ep->t;
}
else break;
}
if(k<i)
{
tnum=str[k];
Edge* ep=now->e[tnum];
if(str[i-k+ep->l]==id)
break;
else
{
np=p+(tot++);
np->dep=i-1-(k-1)+now->dep;
np->add(str[i-k+ep->l],i-k+ep->l,ep->r,ep->t);
now->modify(tnum,ep->l,i-k-1+ep->l,np);
}
}
else if(now->e[id]!=NULL)
break;
else np=now;

Node* nl=p+(tot++);
np->add(id,i,n,nl);
nl->dep=np->dep+n-i+1;

if(old!=Root)
old->slink=np;
old=np;
now=now->slink;
}
if(old!=Root)
old->slink=now;
}
}

int f[MAX],g[MAX],first,last;
Node* que[MAX];

void calc()
{
int i,j,k;
Node* u;
que[first=last=1]=Root;
++last;
while(first<last)
{
u=que[first++];
for(j=u->exi,i=getnum(j&(-j));j;j-=(j&(-j)),i=getnum(j&(-j)))
que[last++]=u->e[i]->t;
}
for(k=last-1;k>=2;--k)
{
u=que[k];
if(u->exi==0)
u->time++;
for(j=u->exi,i=getnum(j&(-j));j;j-=(j&(-j)),i=getnum(j&(-j)))
u->time+=u->e[i]->t->time;
f[u->dep]=max(f[u->dep],u->time);
}
g[n]=n;
for(i=n-1;i>=1;--i)
{
f[i]=max(f[i],f[i+1]);
if(f[i]==f[i+1])
g[i]=g[i+1];
else g[i]=i;
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("string.in","r",stdin);freopen("string.out","w",stdout);
#endif
int i,Q;
scanf("%d%d",&n,&Q);
scanf("%s",str+1);
str[n+1]='z'+1;++n;
for(i=1;i<=n;++i)
str[i]-='a';
BuildSuffixTree(str,n);
calc();
for(i=1;i<=Q;++i)
{
int l,r;
scanf("%d %d",&l,&r);
printf("%d %d\n",f[l],min(g[l],r));
}
return 0;
}



  评论这张
 
阅读(556)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018